算法很美（如何找数组中唯一成对的那个数）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法很美（如何找数组中唯一成对的那个数），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2429字，纯文字阅读大概需要4分钟。

内容图文

大家关注微信公众号 罡罡同学 回复蓝桥杯

可免费获得历年真题和C语言版的真题源代码

算法很美（如何找数组中唯一成对的那个数）

异或^

A^A=0
A^0=A
A^A ^B=B
交换律：A^B ^C=A ^C ^B
结合律：A^B ^C=A ^(B ^C)

题目:
1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将他找出来；不用辅助存储空间，能否设计一个算法实现？

刚开始的想法是，直接排序，然后相邻的元素进行对比不就好了？
但后来发现没有这么简单，题目要求，每个数组元素只能访问一次。
错误代码：

import java.util.Arrays;
import java.util.Random;
public class Main {
	public static void main(String[] args) {//错误示例
		int N=1001;
		int[] a=new int[N];
		for(int i=0;i<a.length-1;i++){
			a[i]=i+1;
		}
		//最后一个数是随机数
		a[a.length-1]=new Random().nextInt(N-1)+1;
		search(a);
	}

	private static int search(int[] a){
		Arrays.sort(a);
		for(int i:a){
			System.out.print(i+" ");
		}
		int tag=a[0];
		for(int i=0;i<a.length-1;i++){
			if(a[i]==a[i+1]){
				tag=a[i];
			}
		}
		System.out.println("\n" +tag);
		return tag;
	}
}

正确思路：1.先建立一个1001大小的数组 2.将1-1000的数字填充进数组中
3.在随机产生一个1-1000的随机数 4.利用异或原理

先用1…k…k.1000异或，然后再和(1^…k…1000)异或，我们发现，有3个K，其他元素只有2个，那么两个的元素都被异或约掉了，那么只剩下最后一个元素，也就是我们所求的K（巧妙呀！哈哈）

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int N=1001;
		int []arr =new int[N];
		//	前N-1位为从1到N-1
		for(int i=0;i<N-1;i++){
			arr[i]=i+1;
		}
		//	第N位为随机产生的一个1到N-1的数字
		arr[N-1]=new Random().nextInt(N-1)+1;
		for(int i=0;i<N;i++){
			System.out.print(" "+arr[i]);
		}
		//	利用异或运算
		int x=0;
		for(int i=1;i<N;i++){
			x=x^i;
		}
		for(int i=0;i<arr.length;i++){
			x=x^arr[i];
		}
		System.out.println("\n唯一成对的那个数是："+x);
	}
}

方法二：开辟辅助空间，进行暴力破解
思路：原数组中每出现一个值，就对该值为下标的辅助数组值加一；辅助数组的意思就是记录值为下标的数字出现了几次。
代码:

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int N=1001;
		int []arr =new int[N];
		//	前N-1位为从1到N-1
		for(int i=0;i<N-1;i++)
		{
			arr[i]=i+1;
		}
		//	第N位为随机产生的一个1到N-1的数字
		arr[N-1]=new Random().nextInt(N-1)+1;
		for(int i=0;i<N;i++)
		{
			System.out.print(" "+arr[i]);
		}
		//	方法二：开辟辅助空间，进行暴力破解
		int []b=new int[N];
		for(int i=0;i<N;i++)
		{
			b[arr[i]]++;
		}
		for(int i=0;i<N;i++)
		{
			if(b[i]==2)
			{
				System.out.println("\n唯一成对的数是"+i);
			}
		}
	}
}

部分参考原文

谢谢大家的支持，您的一键三连是 罡罡同学前进的最大动力！

一键三连 一键三连 一键三连 一键三连 一键三连 一键三连

内容总结

以上是互联网集市为您收集整理的算法很美（如何找数组中唯一成对的那个数）全部内容，希望文章能够帮你解决算法很美（如何找数组中唯一成对的那个数）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---