关于异或的算法题

medie2005 2007-12-27 07:37:47

加精

有n个32位无符号整数，求其中异或之后结果最大的两个数。
O(n^2)的算法就不要拿出来了。

...全文

2973 77 打赏收藏转发到动态举报

写回复

用AI写文章

77 条回复

切换为时间正序

请发表友善的回复…

发表回复

超级大笨狼 2011-06-27

打赏
举报

鄙视All

这个可以做到O(32*N)的
首先
一，遍历集合，判断所有数字的最高位，从32起，是否存在1和0两种，记录位置。
二，重复一的步骤，只记录同时存在1和0的，都是1或者都是0的数据，下次循环忽略。
三，到最低位时候，就得到了结果。

参考：
http://blog.csdn.net/superdullwolf/archive/2009/10/10/4649080.aspx
http://www.cnblogs.com/dullwolf/archive/2011/06/23/2087954.html

xiaowuRJ 2011-02-27

打赏
举报

虽然发现你这个帖子是几年前发出的了，也不知道你是否已经找到了满意的答案。不过我这里有一个可行的方案就和你分享下。
字典树可以解决这题。
1、建一棵空字典树，然后把每个数的二进制表示从高位到低位插入字典树中。
2、对于第i个数ai,从字典树的根节点出发，一直往下走，如果ai的当前位为p(0或者1),则判断当前走到的节点的p^1儿子节点是否是空，如果不是空，就沿p^1儿子节点走，否则，沿p儿子走.走到叶子节点，就找到了和ai异或最大的数了(当然不排除这个数ai是相同的，当一走都是沿p儿子节点走的时候就是这样的情况了)。

顺便说一下，这个问题和POJ 3764 是一样的，你可以百度一下 POJ3764，就可以找到这个题的结题报告了。
题目网址是： http://poj.org/problem?id=3764

附上本人较拙的代码：
/*
最长异或和路径(字典树)
题目描述:给定一棵n个点的带权树，求树上最长的异或和路径
我们可以通过一遍dfs得到从根到任意节点的异或和记为a[i],那么在树中找一条路径等价于找
两个点
这两个点代表了树上的一条路径，设这两个点位u,v,公共祖先为w,那么距离为
(a[u]^a[w])^(a[v]^a[w])=a[u]^a[v]
我们对这个a序列构建字典树，然后每次从高位到低位贪心的看是否有与之相反的位存在，
然后降路径下去即可
这样选取的一定是最大的，高位的1能要就要，显然保证了最大，那么整个复杂度为31*n
*/

#include <stdio.h>
#include <memory>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
const int N = 100000;
const int D = 2;
const int S = 31;
struct node{
//bool flag;
node* next[D];
}*head;
node num[N*20];
struct e{
int v, nxt, w;
}es[N*2];

int bits[S];
int fir[N], val[N];
int n, en, top;
char str[S*2];
void pre(){
bits[0] = 1;
int i;
for(i = 1; i < S; i++) bits[i] = bits[i-1] << 1;

}
void new_node(node* & p){
p = &num[top++];
//p->flag = true;
int i;
for(i = 0; i < D; i++) p->next[i] = NULL;
}

void add_e(int u, int v, int w){
es[en].v = v, es[en].nxt = fir[u], es[en].w = w, fir[u] = en++;
}

bool input(){
if(scanf("%d", &n) == EOF) return false;
int i;
en = top = 0;
int u, v, w;
for(i = 0; i < n; i++) fir[i] = -1;
for(i = 1; i < n; i++){
scanf("%d%d%d", &u, &v, &w);
add_e(u, v, w);
add_e(v, u, w);
}
return true;
}

void dfs(int id, int w, int f){
val[id] = w;
int v, cur;
for(cur = fir[id]; cur != -1; cur = es[cur].nxt){
if((v = es[cur].v) != f){
dfs(v, w ^ es[cur].w, id);
}
}
}

void insert(char* str){
node* p = head;
int i, j, k;
for(i = 0; str[i]; i++){
k = str[i] - '0';
if(!p->next[k]) new_node(p->next[k]);
p = p->next[k];
}
}

int findMax(int v){ //找以v为一个端点的最长异或路径
node* p ;
int i, j, k;
p = head;
int ans = 0;
for(j = S - 1; j >= 0; j--){
k = v & bits[j];
if(k) k = 1;
if(p->next[k ^ 1]){
p = p->next[k ^ 1];
ans += bits[j];
}else{
p = p->next[k];
}
}
return ans;
}

void solve(){
dfs(0, 0, -1);
int i, ans = 0, j, k;
new_node(head);
for(i = 0; i < n; i++){
k = val[i];
for(j = S - 1; j >= 0; j--) str[j] = (k & 1) + '0', k >>= 1;
str[S] = '\0';
insert(str);
}
for(i = 0; i < n; i++){
ans = max(ans, findMax(val[i]));
}
printf("%d\n", ans);
}

int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
pre();
while(input()) solve();
return 0;
}

如还有疑问，就Q我吧： 710102161

昊叔 2008-01-10

打赏
举报

基数排序，再动态规划

HW121 2008-01-02

打赏
举报

追求效率而言还是用各种排序方法思想，重新改写，只需找到异或之后结果最大的子集，而非全部排序。

HW121 2008-01-02

打赏
举报

这道题与【有n个32位无符号整数，求其中两个数和最接近0x80000001】是等价的

如果排好序从两端往中间比对就可O(n)，开始看到mathe说到M位全部取反,还认为与我心中算法一致，仔细看了mathe算法过程，二分法查找这一步可改两端往中间比对。

所以我一直在琢磨O(n)方法，排序算法中基数排序是O(n)，但空间也是O(n)，所以想到基数排序按值域分区间方法，但改先从高位向低位顺序，这正好与Tiger的算法一致。如果把按值域分区间方法改为浮动的，先求出开始值落在第i趟值域，先按i趟值域扫，当出了值域则将当前计数好的值域换到新的值域，再从这趟值域往下扫，这样处理可以加快数据值域分布不均的情况。对这道题我认为取16为底的基数处理较好。只需要多开16对int空间，可以一次完成4位的处理。

flyingwow99 2007-12-29

打赏
举报

我的想法是
一遍扫描
按最高位1是哪个bit，分成 0----31组，
各组个数为n[0] ....n[31]
那么问题所求的两个数其中一个一定在满足这个条件第m组： n[m]>0, n[k]==0(k=m+1 .. 31)
接下来还有什么办法优化就想不清楚了，，，
楼下继续

imlmm 2007-12-29

打赏
举报

我觉得应该是O（n）的复杂度

flyingscv 2007-12-29

打赏
举报

Tiger_Zhao 的办法不多，不过实现起来也很麻烦

至于最笨的的方法，O(n!)应该是打不住的 ^_^

Tiger_Zhao 2007-12-29

打赏
举报

48楼：不用想了，看我21楼。

Vitin 2007-12-29

打赏
举报

一个笔误：...特别在n远小于2^M时会比较明显...

Vitin 2007-12-29

打赏
举报

同意mathe，复杂度单看数量级O(xx)是不够的。特别对于类似这样有规模限制（32位数）的算法。
因此几种算法的实际复杂度都差不多，在扩展为无限制时(64位，128位，...，任意位)则会有区别。

不过我觉得Tiger的算法还是很好的。它的空间复杂度可以保持在min(O(n),O(2^M))。当空间复杂度为O(2^M)时，时间复杂度是O(M*n)；当空间复杂度是O(n)时，时间复杂度是O(M*n*logn)。（因为不考虑重复数的问题，可以认为n<=2^M，即logn<=M，所以每次插入新组时使用折半查找的话平均时间可以看作min(logn，M)=logn）。所以，在空间足够多的时候，可以期待在最坏情况下复杂度达到O(M*n)；而在空间不够时，最坏情况下复杂度为O(M*n*logn)。
但是实际上，平均情况下不需要O(M*n)或O(M*n*logn)那么多。因为在每一轮会做筛选，n为逐轮下降（特别在n远小于M时会比较明显，这样即使空间不够，而得到O(M*n*logn)的复杂度，也会因n的快速下降而与O(M*n)相差不大）。另外，这个算法的好处是不用对n排序，从而其性能不依赖于n个数的原始分布。

另一方面,medie2005、mathe等的算法也很好，其中mathe的算法可以看作是对medie2005算法的性能改进（一次处理多位+筛选）。而medie2005的算法虽然相比其他算法会慢一些（因为不做筛选），但是它过程最直观，实现起来最简单，同时还完成了一项额外工作：找到了每一个数的最大互补数（这里“最大”意指作异或后的数最大）。无疑这是一个很通用的算法，值得广泛使用和借鉴。

总的来说，这里的许多算法都很好，很有创意，学习一下，呵呵。

HW121 2007-12-29

打赏
举报

用256桶，对折两边计数不为0的桶值的距离，找到最大异或的桶，将这些桶对对应的数据移至前端。
也只需要多加256个int空间，空间复杂O(1)

HW121 2007-12-29

打赏
举报

2、从k位向下，假设第i＋1位已完成，第i位扫描m个已分1、0位子集（可由k位断大小），对于子集，重新按k位和i位

HW121 2007-12-29

打赏
举报

因为代码没写完，公司要我们先回家，先把思路说下：
1、找第一次同时出现1、0位的k位，分1、0位两个区间, 异或最大值1<<k。
2、从k位向下，假设第i-1位已完成，第i位扫描m个已分1、0位子集（可由k位断大小），对于子集，重新按k位和i位，
再分出两个这样子集【[00,10][01,11]】，有对的子集排在前面，无对的子集排在后面（丢去），只要i位有子集，异或最大值或上1<<i，
有效长度为子集总长，若i位分不出则子集总长不变至i-1位。
3、重复2至为0，最后子集为所求。

这样时间复杂度O(n)，n较小时因分子集，对半分为总长缩小最慢，故应该比 nlbn 要小（除前面第1步外）。

另外可以用256桶，对折两边计数不为0的桶值，找到最大异或的桶，将这些桶对，移至前端，可加速。

mathe 2007-12-29

打赏
举报

在45楼我对算法做过修改了，修改以后，时间复杂度就一样了，可以看成O(n*M)
至于说基数排序，通常只是对输入数据分布很均匀很有规律的情况才做的。
对于这道题目，当然如果n>=4G时，排序完全可以通过基数排序做（其实可以做的更好，因为重复的数据我们不需要考虑，我们只要记录任意一个数据是否出现，所以对于这种情况，用我的方法，即使有排序（这时排序代价很小），不会比Tiger的方法差。
而对于n<4G的情况，快速排序虽然时间复杂度为O(n log(n)),但是花费的时间同Tiger的算法相比要远远小于他的算法.实际上这时log(n)总是小于32的。实际上快速排序算法是类似的代码执行log(n)趟，而tiger的算法是相同的代码执行32趟。而这个算法为了保持形式上的O(n),每次都需要重新复制所有的数据，导致每一趟处理要慢很多。
当然从总体上来说，上面的这些算法基本上复杂度都差不多，所差的就只是一个常数倍而已。而我在上面反复所要强调的是，算法时间复杂度不能那样算，把这个都看成O(n)了。

imlmm 2007-12-29

打赏
举报

由于上面算法过程每步都不会超过O(nlog(n)),而总共迭代步数不超过数据总位数M( M=O(log(n)) ),所以总复杂度为O(n log^2 (n))
--------------
你的算法没有怎么看明白。。。：（
不过最大bit数 M 应该和 N 没有关系吧吧。。。（n个数的最大bit位和n等于几没有直接联系）。因此，你的算法计算次数是 n*log(n)*M
在已知M的情况下，也可以我或者tiger的算法改为最多计算 M*n 次，其中 M 是经过n次比较找到的一个 0 到 32之间的常数，复杂度也是O（n）

Efcndi 2007-12-29