有n个32位无符号整数，求其中异或之后结果最大的两个数

x642458 2010-05-11 12:06:12

有n个32位无符号整数，求其中异或之后结果最大的两个数。
O(n^2)的算法就不要拿出来了
要求：所用内存尽量小点，n>=100000;

...全文

2218 23 打赏收藏转发到动态举报

写回复

用AI写文章

23 条回复

切换为时间正序

请发表友善的回复…

发表回复

Sunday 2010-05-19

打赏
举报

http://zhuyingqingfen.download.csdn.net/

sluogang 2010-05-17

打赏
举报

using System;
using System.Collections;
using System.Collections.Generic;

namespace xor
{
class Node
{
Node[] _childen = new Node[2];

public Node() { IsLeaf = false; }
public Node(Leaf value) { IsLeaf = true; Value = value; }

public bool IsLeaf { get; private set; }
public Leaf Value { get; private set; }
public Node[] Children { get { return _childen; } }
}

class Leaf
{
private const int PATH_COUNT = 32;
public int Value { get; private set; }
public int[] Path { get; private set; }

public Leaf(int value)
{
Value = value;
Path = new int[PATH_COUNT];
GeneratePath();
}

private void GeneratePath()
{
for (int i = 0; i < Path.Length; i++)
{
bool f = ((Value & (((int)1) << i)) != 0);
if (f)
{
Path[i] = 1;
}
}
}
}

class Pair
{
public Pair(Node a, Node b) { A = a; B = b; }
public Node A { get; private set; }
public Node B { get; private set; }

#region 用于比较的部分
public override bool Equals(object obj)
{
return Equals(this, obj as Pair);
}

public override string ToString()
{
return ToString(A, B);
}

private string ToString(Node a, Node b)
{
return string.Format("{0}:{1}", a.Value == null ? "NULL" : a.Value.Value.ToString(), b.Value == null ? "NULL" : b.Value.Value.ToString());
}
private string ToXString()
{
return ToString(A, B);
}

private string ToYString()
{
return ToString(B, A);
}

public bool Equals(Pair a, Pair b)
{
if (a == null && b == null)
{
return true;
}
if (a != null && b != null)
{
string ax = a.ToXString(), ay = a.ToYString(), bx = b.ToXString();
if (ax == bx || ay == bx)
{
return true;
}
}

return false;
}
#endregion
}

class Program
{
private const int MAX = 2000000000; //最大数字的值
private const int COUNT = 100000;

private static Node root = new Node();

static void Main(string[] args)
{

int[] values = GenerateValues();

#region 算法计算结果部分
DateTime a1 = DateTime.Now;
IList<Pair> ps = Do(values);
IList<Pair> all = new List<Pair>(ps.Count);

if (ps != null && ps.Count > 0)
{
foreach (Pair p in ps)
{
int A = p.A.Value.Value, B = p.B.Value.Value, C = A ^ B;

Console.WriteLine("A[{0}] B[{1}]: {2}", A, B, C);
}
}
DateTime a2 = DateTime.Now;
Console.WriteLine("{0}", a2 - a1);
#endregion

#region 正常的，用于验算
/*
DateTime b1 = DateTime.Now;

int max = 0, a = 0, b = 0;
for (int i = 0; i < values.Length; i++)
{
for (int j = 0; j < values.Length; j++)
{
int x = values[i], y = values[j];

if (x != y)
{
int z = x ^ y;
if (z > max)
{
max = z;
a = x;
b = y;
}
}
}
}
Console.WriteLine("A[{0}] B[{1}]: {2}", a, b, max);
DateTime b2 = DateTime.Now;
Console.WriteLine("{0}", b2 - b1);
*/
#endregion

Console.Read();
}

#region 算法部分
private static IList<Pair> Do(int[] values)
{
PrepareTree(values);
return Pop(new Pair[] { new Pair(root, root) });
}

private static void SafeAdd(IList<Pair> pairs, Pair pair)
{
if (!pairs.Contains(pair))
{
pairs.Add(pair);
}
}
private static IList<Pair> Pop(IList<Pair> pairs)
{
List<Pair> newPairs = new List<Pair>(pairs.Count * 2);

foreach (Pair pair in pairs)
{
if (pair.A.Children[0] != null && pair.B.Children[1] != null)
{
SafeAdd(newPairs, new Pair(pair.A.Children[0], pair.B.Children[1]));
}

if (pair.A.Children[1] != null && pair.B.Children[0] != null)
{
SafeAdd(newPairs, new Pair(pair.A.Children[1], pair.B.Children[0]));
}
}

if (newPairs.Count == 0)
{
foreach (Pair pair in pairs)
{
if (pair.A.Children[0] != null && pair.B.Children[0] != null)
{
SafeAdd(newPairs, new Pair(pair.A.Children[0], pair.B.Children[0]));
}

if (pair.A.Children[1] != null && pair.B.Children[1] != null)
{
SafeAdd(newPairs, new Pair(pair.A.Children[1], pair.B.Children[1]));
}
}
}

if (newPairs.Count == 0)
{
return null;
}
else
{
if (newPairs[0].A.IsLeaf)
{
return newPairs;
}
else
{
return Pop(newPairs);
}
}
}

private static void AddToTree(Leaf leaf)
{
Node node = root;
for (int i = leaf.Path.Length - 1; i > 0; i--)
{
int idx = leaf.Path[i];
if (node.Children[idx] == null)
{
node.Children[idx] = new Node();
}
node = node.Children[idx];
}
node.Children[leaf.Path[0]] = new Node(leaf);
}

private static void PrepareTree(int[] values)
{
for (int i = 0; i < values.Length; i++)
{
AddToTree(new Leaf(values[i]));
}
}
#endregion

/// <summary>
/// 产生不重复的数字数组。
/// </summary>
/// <returns></returns>
private static int[] GenerateValues()
{
int[] vs = new int[COUNT];
BitArray bs = new BitArray(MAX);

Random rnd = new Random();

for (int i = 0; i < COUNT; i++)
{
int v = rnd.Next(MAX);
while (bs[v])
{
v = rnd.Next(MAX);
}

bs[v] = true;
vs[i] = v;
}

return vs;
}
}
}

qq120848369 2010-05-16

打赏
举报

结贴！

超级大笨狼 2010-05-16

打赏
举报

以后在这个版块回答问题不写代码了，太耗费精力了，耽误了工作和生活。

只提供思路就可以渡人成佛了。

超级大笨狼 2010-05-16

打赏
举报

我这几天想出来答案了，以前我写的代码先否定掉。

下边是思路，具体代码不写了，二进制调试代码太费脑子了。

我们定义MaxXor为异或后最大值，Boy是其中较大的数，Girl是小的那个

1，先在O(n)时间内求出最高的位K。

2，从最高位K开始，
判断条件一：在数组里是否存在K位1的数.
条件二：存在K位是0的数.

只有一和二都满足，那么最大异或才有可能在K这里产生1，
（因为1^0=1;1^1=0;0^0=0）
MaxXorK记录一个1在K的位置。否则记录一个0。

判断条件一，二循环那数组，最坏的情况下是O(n)，我们把这个复杂度假设是O(m)
多数情况下，会提早找出一二条件，提前退出

如果一满足，二不满足，在该位置记录Boy和Girl都记录1
如果二满足，一不满足，在该位置记录Boy和Girl都记录0

3，从K-1位开始，重复上述步骤，到K=1的时候。
就找到了MaxXor，Boy和Girl

总的复杂度最坏是K*O(m),实际上由于离散分布，O(m)远远小于O(n)
且K是有限的，最大是31，正整数是32位嘛。
所以，总体复杂度是O(n)

超级大笨狼 2010-05-14

打赏
举报

using System;
using System.Collections.Generic;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
int n = 100 * 100;//一百万，测试时请减少这里
int[] Arr = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++)
{
Arr[i] = rand.Next(int.MaxValue);//全部整数内，测试时请减少这里
}

int MaxDigit = 0;//最高位
for (int i = 0; i < Arr.Length; i++)
{
//O(n)时间找出最高位
int digit = (Arr[i] == 0) ? 0 : 1 + (int)(Math.Log(Arr[i]) / Math.Log(2));
if (MaxDigit < digit) { MaxDigit = digit; }
}
//int Max_Seriate_1 = 0;//找出最大连续的1，并且有相应数字的0
int mask = 0;
int k = 1;
int maxXOR = 0;
//最外层循环是32次内，里层循环会提前中断，所以复杂度远远小于32*O(n),还是O(n)级别的。
for (k = 1; k <= MaxDigit; k++)
{
mask = ((1 << k) - 1) << (MaxDigit - k);//产生前K个1的蒙板
bool HasFound = false;
bool Has_K_1_Head = false;
bool Has_K_0_Head = false;
for (int i = 1; i < Arr.Length; i++)
{
if ((Arr[i] & mask) == mask)
{
Has_K_1_Head = true;
}
if ((Arr[i] & mask) == 0)
{
Has_K_0_Head = true;
}
if (Has_K_1_Head && Has_K_0_Head)
{
HasFound = true;
break;
}
}
if (!HasFound)
{
maxXOR ^= (1 << (k - 1));//第k位是1
}
else
{
maxXOR ^= ~(1 << (k - 1));//第k位是0
}
}
maxXOR = (maxXOR < 0) ? (-maxXOR - 1) : maxXOR;
Console.WriteLine("最大XOR="+maxXOR);
//找到了最大的maxXOR，再回去找那两个数，可以用Hash在O(n)时间内找出
//不过大的哈希在我机器上，.NET自带的不灵，先暂时写到这里。
//可以用二叉树，在O(N*LogN)时间内;
HashSet<int> A=new HashSet<int>(Arr);
foreach (int a in A)
{
if (A.Contains(maxXOR ^ a))
{
Console.WriteLine("是由" + a + "和" + (maxXOR ^ a) + "产生的");
break;
}
}

//以下是用暴力循环在O(n^2)级别的测试准确度对比部分
//请减少输入规模和离散程度，一般n=100就可以
//因为暴力循环肯定可以得到结果，所以暴力循环的结果是正确的。
//如果两个结果一致，那么算法正确。

//List<int> XOR = new List<int>();
//for (int i = 0; i < Arr.Length; i++)
//{
// for (int j = 0; j < Arr.Length; j++)
// {
// XOR.Add(Arr[i] ^ Arr[j]);
// }
//}
//XOR.Sort();
//Console.WriteLine("maxXOR=" + XOR[XOR.Count - 1]);
Console.Read();

}
}
}

绿色夹克衫 2010-05-13

打赏
举报

今天起猛了，写了个大概其的，没仔细验证，大家帮忙看看有什么问题没有！

using System;

namespace CSharpTest
{
class Program
{
static int[] Items;
public static void Main()
{
Items = new int[] { 1, 3, 7, 15, 16, 17 };
Array.Sort(Items);
int hBit = (int)Math.Log(Items[Items.Length - 1], 2);
int mid = FindMid(0, Items.Length - 1, hBit);
Console.WriteLine(SearchMaxXor(0, mid - 1, mid, Items.Length - 1, hBit));
Console.ReadKey();
}

static int SearchMaxXor(int lowerL, int upperL, int lowerH, int upperH, int currentBit)
{
if (lowerL == upperL && lowerH == upperH || currentBit == -1)
return Items[lowerL] ^ Items[lowerH];

int midL = FindMid(lowerL, upperL, currentBit);
int midH = FindMid(lowerH, upperH, currentBit);

if (midL == -1 || midH == -1)
{
if (midL == -1) midL = lowerL;
if (midH == -1) midH = lowerH;
return SearchMaxXor(midL, upperL, midH, upperH, currentBit - 1);
}

int maxL = SearchMaxXor(lowerL, midL - 1, midH, upperH, currentBit - 1);
int maxH = SearchMaxXor(midL, upperL, lowerH, midH - 1, currentBit - 1);
return Math.Max(maxL, maxH);
}

//用二分也许还可以稍快一点，但复杂了，并且整体复杂度未见下降
static int FindMid(int lower, int upper, int currentBit)
{
int currentXor = 1 << currentBit;

if ((Items[upper] & currentXor) == 0)
return -1;

for (int i = lower; i <= upper; i++)
if ((Items[i] & currentXor) != 0)
return i;

return -1;
}
}
}

jiaoguohui 2010-05-13

打赏
举报

1楼提供的连接中的方法2，简单易懂，好实现，不错

qq120848369 2010-05-12

打赏
举报

很好..我也能看懂位运算了,HOHO.

绿色夹克衫 2010-05-12

打赏
举报

估计想一下找到某一个数，再和其他数验证的方法不太可行。

以前碰到过类似的问题，比本题还要复杂一些吧，主要思想还应该是分治，配合剪枝的话，可以达到比Trie更快的效果。Trie虽然号称O(n)，但O = 32，已经大于Log(n)了。

这是原题的地址：http://acm.timus.ru/problem.aspx?space=1&num=1318

LZ可以写这样一个函数

SearchMaxXor(int lowL, int upperL,int lowH, int upperH, int currentBit)

前提是有序，不断地按照当前位把数组分为两段，递归下去，是个n*log(n)的方法，并且不用额外开空间。

超级大笨狼 2010-05-12

打赏
举报

oo说的对，晚上我回家改进下算法。
假设开始是A,挑选高位后是B，其他的是C.

循环中逻辑应该是：

如果去势后，B有高位，C有非高位，可能在此位产生最大，则删除掉B里的其他低位数字。O(n)
（
如果B无高位，C有高位，也可能在此位产生最大，则对B不做任何操作。
如果B无高位，C无高位，则不可能在此位产生最大，则对B不做任何操作。）

进入下一次“去势”循环.

oo 2010-05-12

打赏
举报

int Boy = Arr[B.First()];
最后boy还是从B里取的啊，如果第二步10000从B里删除了，那10000就不会成为最后的boy，另外1111也不会，因为=1111不会分到B组

超级大笨狼 2010-05-12

打赏
举报

手误：A^(1<<（位数-1）)就可以去掉最高位。
叉下自己

超级大笨狼 2010-05-12

打赏
举报

写了一个O(n)的，大家评估一下，今天太晚了，就不做测试验证准确性了。
先说一下思路：

1，先比较位数高度不同的XOR运算，观察两组数

假设第一组是五位的10001^11=10010，第二组是四位1001^11=1010
可以知道,XOR运算就是按照矮的数给高的数，按1的位取反，。
我们可以知道高位数运算的结果肯定要比矮位数要大。
我把高的那个叫Boy,矮的叫Girl，形象些。
XOR好比强J,不管谁插了谁，如果Boy位数高，那么生下的野种肯定比位数底的结果要大。
所以，我们第一步：寻找位数最高的Boy们,故事肯定发生在它们身上,我们叫他们“纯爷们儿”！
这一步耗时O(n)

2，第2步，观察高度相同的Boy,谁XXOO后会更牛呢？
既然最高位都相同，那么我们就都去掉他再比较，利用A^(1<<位数)就可以去掉最高位。
想不明白的叉下自己。我们管这个过程叫做“去势”，“去势”在兽医学里也叫阉割。
“去势”后的boy可能矮人好几节，比如10010,去掉左边的1，立马就成了10。够衰的。
需要和原先不是Boy，站在一起，再挑真正的Boy，在纯爷们儿中再挑纯爷们儿。
“去势”一次耗时O(n)，在int32这个地球世界里，最高不到32位，所以即使大家都是阿凡达，也架不住，
所以，最糟糕32*O(n)，大家说复杂度是几？O(n)！回答正确！

3，挑选到什么时候结束呢？
剩下一个纯爷们儿！~~回答正确，或者"去势"到了无势可去。
我可以肯定的告诉你，随机分布的"去势"过程中，绝对不会有那么多纯爷们够刀的，因为迅速收敛，远远早于32次，就会找到男人中的男人。

4，找到了这个人渣，那么我们就再让他XXOO所有的女人，把结果找最大的，时间当然是O(n).
如果这个都怀疑的，叉一下自己。

下边给出代码，因为今天前半夜，一是没想出来，二是被其他事情耽误了，都夜里2点多了，才把代码实验出来。回头我有时间再验证是否有Bug手误什么的，大家先评估下思路。



using System;

using System.Collections.Generic;

namespace ConsoleApplication3

{

    class Program

    {

        static void Main(string[] args)

        {

            int n = 1000*1000;//一百万

            //int n = 100;//一百万

            List<int> Arr = new List<int>(n);

            Random rand = new Random();

            for (int i = 0; i < n; i++)

            {

                Arr.Add(rand.Next(int.MaxValue));

            }



            int maxDigit = 0;//最高位

            List<int> A = new List<int>(Arr);//复制一份做运算。





            for (int i = 0; i < A.Count; i++)

            {

                //O(n)时间找出最高位

                int digit = (A[i] == 0) ? 0 : 1 + (int)(Math.Log(A[i]) / Math.Log(2));

                if (maxDigit < digit) { maxDigit = digit; }

            }

            HashSet<int> B = new HashSet<int>();

            

            maxDigit--;

            for (int i = 0; i < A.Count; i++)

            {

                //O(n)时间找出最高位的那些数字，//去掉最高位。记录索引

                if (A[i] >> maxDigit > 0)

                {

                    A[i] ^= (1 << maxDigit); //去掉最高位。                   

                    B.Add(i);

                }

            }

            

            //O(最大位数*n)时间，最大位数<32常数,所以还是=O(n)时间，找出最高位的那些数字 

            while (maxDigit > 1 && B.Count > 1)

            {

                maxDigit--;

                for (int i = 0; i < A.Count; i++)

                {

                    //O(n)时间找出最高位的那些数字，//去掉最高位。 

                    if ((A[i] >> maxDigit) > 0)

                    {

                        A[i] ^= (1 << maxDigit);//去掉最高位。

                    }

                    else

                    {

                        //删除那些不在最高位的B的索引,取交集。

                        if (B.Contains(i))

                        {

                            B.Remove(i);

                            if (B.Count == 1)

                            {

                                break;

                            }

                        }

                    }

                }

            }

            int Boy = Arr[B.First()];

            int Girl =-1 ;

            int MaxXor = 0;

            //O(n)时间找出异或最大值。

            for (int i = 0; i < Arr.Count; i++)

            {

                int Xor = Boy ^ Arr[i];

                if (Xor > MaxXor)

                {

                    MaxXor = Xor;

                    Girl = Arr[i];

                }

            }             

            if (B.Count == 1)

            {

                Console.WriteLine("最大异或数是" + MaxXor + "，是由" + Boy + "和" + Girl + "产生的,总复杂度是O(n)");

            }

            Console.Read();  

        }



    }

}