TELNET连接到SMTP服务器发送邮件
代码缩进工具 indent
Oct
30
题目：给出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++)，如果有误，还望指出：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
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;
}
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 。
ps, 所谓快速划分能达到 O(N), 只是理论值, 实际上效果并不好, momodi 那种做法可是实打实的 O(N), 系数是 2 不是 3, 空间是多两个, 在将所有数划分为 a, b 两半的时候就可以分别异或了
momo的方法当然是最好，所以放在前面了阿