找不同的数据.( 我是长标题)

cat_old 发布于 2013/05/31 14:54
阅读 269
收藏 0
有一个数组,假如有一百万个数据,其中有一个的值与其他的不同。
如何在最短时间内将这个数据找出来
要求:不要开辟新的使用空间,如使用哈希表
不要使用判断语句,如if
求解 
加载中
0
南湖船老大
南湖船老大

用数学的方法,求和,取模如何?

比如 998,998,998,445,998...

加和,对998取模,得到的结果是445,就是要找的数字。

补充:又回想了下,发现这个方法有问题,一百万数据的求和有溢出问题。。。这个题我貌似见过,比我这种做法聪明多了

南湖船老大
南湖船老大
回复 @cat_old : 我这方法可行,但数据会溢出,不好不好
cat_old
cat_old
恩 能不能写出来呢 我也不是很明白的 我从网上看到的题目
0
HandMU
HandMU

引用来自“阿尔法兽”的答案

用数学的方法,求和,取模如何?
确实可以
0
吐槽的达达仔
吐槽的达达仔

一个值不同?遍历一次就好了~~

你无论何种方式都要做一个遍历吧~~!最多就是100万数据,可以并发地来做遍历。

0
linan
linan
public static int find(int[] array) {
		int result = 0;
		for (int i = 0; i < array.length; i++) {
			result ^= array[i];
		}

		return result
				^ (array[0] == array[1] ? array[0]
						: array[0] == array[2] ? array[0] : array[1]);
	}
满足你要求不?
linan
linan
回复 @莲莲莲 : x^x=0,x^0=x ; a^b=c , c^b=a, c^a=b ;
莲莲莲
表示后面return那段看不懂!再异或下有什么意义。
Z_wenuw
Z_wenuw
看了一楼本来想说位操作的,结果大神在这里。
南湖船老大
南湖船老大
貌似我见过的标准答案就是这个
返回顶部
顶部