突然發(fā)現(xiàn)以前回答過的網(wǎng)上的一個(gè)題目呻纹，
1 有一個(gè)數(shù)組鸳碧，假如有一百萬個(gè)數(shù)據(jù)蕴茴，其中有一個(gè)的值與其他的不同喂链。如何在最短時(shí)間內(nèi)將這個(gè)數(shù)據(jù)找出來要求：不要開辟新的使用空間，如使用哈希表甥啄，不要使用判斷語句，如if
現(xiàn)在想了下居然有和以前不同的思路。
稍微描述下笆载。
我理解題意為有100萬個(gè)int型，其中99…………個(gè)相同值涯呻，一個(gè)不同值凉驻。
把100萬個(gè)數(shù)字的最低位bit相加，得到一個(gè)數(shù)复罐，這個(gè)數(shù)-1取非涝登，即是不同值的最低位。
其他位效诅，依次如上處理胀滚。即可。
按這尿性算法復(fù)雜度是O(n)乱投，有時(shí)間再想想有沒有優(yōu)化的算法了咽笼。
偽代碼如下：
int unique_value(int data[]) {
int value = 0;
unsigned long long bit = 0;
// 32位循環(huán)處理32次
for(int i = 0; i < 32; i++) {
for(int j = 0; j < 100W; j++) {
// 統(tǒng)計(jì)位上1的數(shù)量
bit += data[j] & (1 << i) >> i;
}
// 算出不同值對(duì)應(yīng)位上是還是0
value |= !(bit - 1) << i;
}
// 返回不同值
return value;
}
代碼沒變異也沒跑過，不知道對(duì)不對(duì)…………
