Oct 30

~找不同 不指定

felix021 @ 2008-10-30 22:59 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(6117) | Via 本站原创 | |
题目:给出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;
}





欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
lzonline01
2011-3-27 10:38
算法一可以改进:对得到的任意一个结果与k异或就是另外一个结果
snoopy
2008-11-7 13:04
为灭你做法的空间复杂度是 O(logN)? 这个没看懂
ps, 所谓快速划分能达到 O(N), 只是理论值, 实际上效果并不好, momodi 那种做法可是实打实的 O(N), 系数是 2 不是 3, 空间是多两个, 在将所有数划分为 a, b 两半的时候就可以分别异或了
felix021 回复于 2008-11-7 13:22
恩,恩,快速划分的时候递归需要堆栈空间撒。。
momo的方法当然是最好,所以放在前面了阿
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]