突然发现以前回答过的网上的一个题目，
1 有一个数组，假如有一百万个数据，其中有一个的值与其他的不同。如何在最短时间内将这个数据找出来要求：不要开辟新的使用空间，如使用哈希表，不要使用判断语句，如if
现在想了下居然有和以前不同的思路。
稍微描述下。
我理解题意为有100万个int型，其中99…………个相同值，一个不同值。
把100万个数字的最低位bit相加，得到一个数，这个数-1取非，即是不同值的最低位。
其他位，依次如上处理。即可。
按这尿性算法复杂度是O(n)，有时间再想想有没有优化的算法了。
伪代码如下：
int unique_value(int data[]) {
int value = 0;
unsigned long long bit = 0;
// 32位循环处理32次
for(int i = 0; i < 32; i++) {
for(int j = 0; j < 100W; j++) {
// 统计位上1的数量
bit += data[j] & (1 << i) >> i;
}
// 算出不同值对应位上是还是0
value |= !(bit - 1) << i;
}
// 返回不同值
return value;
}
代码没变异也没跑过，不知道对不对…………
网友评论