标题：~找不同
出处：Felix021
时间：Thu, 30 Oct 2008 22:59:07 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1243

内容：
题目：给出2N个正数，找出其中两个不凑对的。
e.g.： 
对于1, 2, 2, 3, 4, 5, 3, 4，不凑对的是1和5

算法思路1(momodi给出)：
设不凑对的两个数分别为m和n
1. 对所有数字进行XOR，得出k，则必有k != 0
2. 找到 k 二进制表示中的某一个 1，必有m和n该位分别为1和0
3. 根据该位置为1或0，把所有数分为两a, b半
4. 对a、b两半分别异或，即得出m、n
此算法可以保证正确性，以及O(N)的时间复杂度、O(1)的附加空间。

算法思路2(felix给出)：
1. 如果只剩下一个元素，输出，返回
2. 快速划分成左( <=t ) 右( >t )两块
3. 左边异或得left, 右边异或得right
4. 如果left != 0 && right != 0
     OK，输出left和right，返回
   如果left != 0 返回1处理左边
   如果left == 0 返回1处理右边
此算法"应该"是正确的，但是Felix没有严格证明之。
可以保证O(N)的时间复杂度和O(logN)的附加空间。

贴出Felix的代码(C++)，如果有误，还望指出：
#include<iostream>
using namespace std;

int a[] = {1, 2, 2, 3, 4, 5, 3, 4}; 

void findDiff(int a[], int s, int e){ //e是末尾的下一个
    int i = s, j = e - 1, t;
    if(e - s == 1){ 
        //如果只有1个元素了，必然是答案之一，输出
        cout << a[s] << endl;
        return;
    }
    //随机化，避免退化...
    int random = rand() % (e - s) + s;
    t = a[random], a[random] = a[s];
    if(s < e - 1){
        int left = t, right = 0;
        while(i != j){ //快速划分，并进行异或
            while(i < j && a[j] > t) right ^= a[j], j--;
            if(i != j) a[i] = a[j], left ^= a[i], i++;
            while(i < j && a[i] <= t) left ^= a[i], i++;
            if(i != j) a[j] = a[i], right ^= a[j], j--;
        }
        a[i++] = t; //那个"中间值"

        if(left != 0 && right != 0){
            //都不等于0，就是答案拉!
            cout << left << endl << right << endl;
            return;
        }else if(left != 0){
            //左边不是0? 肯定在这里面，找下去
            findDiff(a, s, i);
        }else{
            //右边不是0? 我找..
            findDiff(a, i, e);
        }
    }
}

int main(){
    findDiff(a, 0, (sizeof(a) / sizeof(int)));
    return 0;
}




Generated by Bo-blog 2.1.0