面试题:在一个数组中有0-99之间的整数101个(数组无序),用高效方法找出其中的唯一的重复元素!

/*
 * 问题:找出101个数据中重复的元素
 * 题目如下:现有0到99,共计100个整数,各不相同,将所有数放入一个数组,随机排布。
 *        数组长度101,多余的数字是0到99其中任意一个数(唯一重复的数字)
 *        请将这个重复的数字找出来
 * 分析:
 *    A:把数组构造出来
 *    B:把数组元素添加进去
 *    C:对数组的元素进去打乱(随机分布)
 *    D:找出重复的元素

 */

这道题有三种方式:第一种用交换排序找出,第二种求数组的和再减去0-99,第三种异或运算求出

源代码如下:

package java基础题目;

/*
 * 问题:找出101个数据中重复的元素
 * 题目如下:现有0到99,共计100个整数,各不相同,将所有数放入一个数组,随机排布。
 *        数组长度101,多余的数字是0到99其中任意一个数(唯一重复的数字)
 *        请将这个重复的数字找出来
 * 分析:
 *    A:把数组构造出来
 *    B:把数组元素添加进去
 *    C:对数组的元素进去打乱(随机分布)
 *    D:找出重复的元素
 */
public class A {
	public static void main(String[] args) {
		int key = (int)( Math.random() * 100);// 产生一个0到99之间的数字
		System.out.println("key="+key);//这个随机生成的重复元素[0,99]
		// A:把数组构造出来
		int[] arr = new int[101];
		// B:添加0到99之间的整数元素到数组中
		for (int i = 0; i < arr.length - 1; i++) {
			arr[i] = i;
		}
		arr[100] = key;//最后一个元素赋值为随机生成的那个重复元素key,(特别注意,在后面打乱数组顺序后,那么重复的元素就可能不在最后了)
		System.out.println("数组的原始顺序是:");
		print(arr);

		// 调用打乱数组的方法
		random(arr);
		System.out.println("数组的打乱后顺序是:");
		print(arr);

		method1(arr);
		method2(arr);
		method3(arr);

	}

	// 生成一个随机的0到99之间的数
	public static void random(int[] arr) {
		// C:对数组的元素进去打乱(随机分布)
		// Math类中的public static double random():产生随机数,范围是[0.0,1.0)
		// int num = (int)(Math.random()*101);//num的取值范围是[0,100]
		//利用for循环1000次
		for (int i = 0; i < 1000; i++) {
			int index1 = (int) (Math.random() * 101);//随机生成2个下标,然后把两个下标对应的数组的值交换,重复1000次基本就打乱了数组的值
			int index2 = (int) (Math.random() * 101);
			// 交换元素
			int temp = arr[index1];
			arr[index1] = arr[index2];
			arr[index2] = temp;
		}
	}

	// 输出函数print  
	public static void print(int[] arr) {
		int len = 0;
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "\t");
			len++;
			if (len % 5 == 0) {
				System.out.println();
			}

		}
		System.out.println("\n--------------------------------");
	}

	// 解决方案一:用交换排序找出重复的元素(效率低)
	public static void method1(int[] arr) {
		A: for (int i = 0; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[i] == arr[j]) {
					System.out.println("用交换排序找出的重复元素是:" + arr[i]);
					break A;// break只能跳出当前的一层循环
				}
			}
		}
	}

	// 解决方案二:求数组的和sum再减去0到99,剩下的
	/*
	 * 接下来,我们用一个比较巧合的做法,我们回来看题目: 现有0到99,共计100个数字,并且还有一个重复数据,这个数据也是在0到99之间 思路:
	 * A:我们把整个数组的所有元素的值给累加起来,是不是就是0到99和那个重复元素一起的和?
	 * B:我们拿这个结果减去0-99的和,那么最终结果就是那个重复的元素
	 * 
	 * 方式二的弊端是:如果计算的数据特别多,就会有数据溢出,所以不好! 更好的方式是:用异或解决!!!!!!
	 */
	public static void method2(int[] arr) {
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
		}
		// 使用sum减去0--99的和,剩下的就是重复的数字
		for (int i = 0; i < arr.length - 1; i++) {
//			sum -= arr[i];//不能这样写,因为数组打乱顺序了,重复元素不一定是最后一个了  比如 12345 3,打乱后 3124 5,最后一个变为5
			sum -= i;
		}
		System.out.println("用求和再减去和的方式找出重复的元素是:" + sum);
	}

	/*
	 * 方式三:异或的一个特点是:x^0^1^2...^99^0^1^2...^99=x
	 * 再看一个式子:0^1^2^...^m...^99^m^0^1^2...^m...^99就等于m,即可找出重复元素的值
	 * 所以,我们使用数组中第一个元素异或后面的所有元素。
	 */
	public static void method3(int[] arr){
		for(int i=1;i<arr.length;i++){
			arr[0] = arr[0]^arr[i];
		}
		//我们再次把arr[0]保存的结果和0,1,2...99的数据异或一次
		for(int i=0;i<arr.length-1;i++){
//			arr[0] = arr[0]^arr[i];//不能这样写,因为数组打乱顺序了,重复元素不一定是最后一个了  比如 12345 3,打乱后 3124 5,最后一个变为5
			arr[0] = arr[0]^i;//注意不是arr[0]^arr[i],数组打乱了顺序
		}
		System.out.println("重复的元素是:"+arr[0]);
	}
}

output:

key=49
数组的原始顺序是:
0	1	2	3	4	
5	6	7	8	9	
10	11	12	13	14	
15	16	17	18	19	
20	21	22	23	24	
25	26	27	28	29	
30	31	32	33	34	
35	36	37	38	39	
40	41	42	43	44	
45	46	47	48	49	
50	51	52	53	54	
55	56	57	58	59	
60	61	62	63	64	
65	66	67	68	69	
70	71	72	73	74	
75	76	77	78	79	
80	81	82	83	84	
85	86	87	88	89	
90	91	92	93	94	
95	96	97	98	99	
49	
--------------------------------
数组的打乱后顺序是:
87	16	35	73	71	
31	72	95	11	48	
15	57	89	1	33	
81	94	54	12	25	
91	5	58	90	46	
32	40	60	75	52	
24	18	83	67	65	
97	86	43	93	39	
7	3	80	70	20	
49	64	78	68	96	
98	6	51	29	10	
42	99	63	50	21	
76	9	41	28	2	
30	8	49	13	37	
53	36	55	69	82	
22	14	44	88	59	
19	45	92	27	34	
77	56	0	47	79	
74	62	26	23	61	
66	38	85	84	4	
17	
--------------------------------
用交换排序找出的重复元素是:49
用求和再减去和的方式找出重复的元素是:49
重复的元素是:49



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。