[讨论]时间换空间算法，散分讨论解决方案

[讨论]时间换空间算法，散分讨论
有过这样一个问题，如何用最小的空间代价得到N个正整数中重复出现过大于N/2次的唯一的一个整数
(N为百万级，乱序，内存限制1M内，时间并没有充裕到允许使用外存...请在算法范畴内解决)

一个经典的做法是时间换空间，做整数分割存储。
建立一个int data[10][10]数组，如果某个数的第i位为j，那么data[i][j]加1.
例如整数123对应data[2][1], data[1][2], data[0][3]
因此，输入N个整数并更新data数组，代码如下：

C/C++ code

int data[10][10] = {0};        int i, j, number, byte, byteValue;        for (i = 0; i < N; ++i)        {            cin >> number;            byte = 0;            do{                byteValue = number % 10;                data[byte++][byteValue]++;                number /= 10;            }while (number);        }

所有数据输入完毕后，那么data中每行值最大的并且大于N/2的数合并起来，就是出现最多的那个数。
问题得到完美解决。

现在的问题是反过来，如果N个数中两两成对出现，如何找出其中唯一的m个单独出现的数呢？(m=1，上面算法可行。然而m>1呢？）
（比如1,2,3,4,5,6,4,3,2,1，希望找出5，6）

[解决办法]
前面一个算法，可以更简单，取第一个数出来放着，后面每次取一个数出来，如果两个数不同则同时踢掉，如果相同则这个数计数累加，最后剩下的那个数即是。时间O(n)空间O(1)
后面一个算法，当m=1时，可以把所有数做异或得到的数即是；当m>1时，可以考虑两个方法，开大数组计数或者维护一个堆，根据数的范围和m/n的大小来决定用哪个方法
[解决办法]
正是这样子，顶一个！

探讨

前面一个算法，可以更简单，取第一个数出来放着，后面每次取一个数出来，如果两个数不同则同时踢掉，如果相同则这个数计数累加，最后剩下的那个数即是。时间O(n)空间O(1)
后面一个算法，当m=1时，可以把所有数做异或得到的数即是；当m>1时，可以考虑两个方法，开大数组计数或者维护一个堆，根据数的范围和m/n的大小来决定用哪个方法

[解决办法]
我觉得不太可能实现
[解决办法]
后一个算法，m>1时，
具体怎么做呢？
[解决办法]
简单一点，时间代价为N<<32

C# code

        public static void outSingle(int[] N)        {            int i = int.MinValue, c;            do            {                c = -1;                foreach (int n in N)                {                    if (n == i && ++c != 0) break;                }                if (c == 0) Console.WriteLine(i);            }            while (++i != int.MinValue);        }
[解决办法]
估计m最多为2。

所有的数异或一下，结果为落单的两个数的异或结果。

针对该结果的二进制表示中，为1的位的位置，
将原来所有的数分为两部分，
一部分该位为0，另一部分该位为1，

两部分分别视为m为1的情况处理。。。
[解决办法]
如果确定存在>N/2
C# code
        public static int moreHalf(int[] N)        {            uint un;            int i, l = (N.Length + 1) >> 1;            int[] c = new int[32];            foreach (int n in N)            {                for (un = (uint)n, i = 0; un != 0; i++, un >>= 1) if ((un & 1) != 0) c[i]++;            }            for (un = 0, i = 31; i >= 0; i--) if (c[i] >= l) un |= 1U << i;            return (int)un;        }
[解决办法]
如果确定存在>N/2,应该是这样
C# code
        public static int moreHalf(int[] N)        {            int v = 0, c = -1;            foreach (int n in N)            {                if (c < 0)                {                    v = n;                    c = 0;                }                else if (v == n) c++;                else c--;            }            return v;        }
[解决办法]
差不多这样子吧：

C/C++ code
for (n=i=0;i<N;i++)   if (n==0) x=a[i], n=1;  else     if (a[i]==x) n++;    else n--;for (n=i=0;i<N;i++)   if (a[i]==x) n++;if (n>N/2) printf("The answer is %d.\n",x);else printf("No answer.\n"); 
 
[解决办法]
所有数据输入完毕后，那么data中每行值最大的并且大于N/2的数合并起来，就是出现最多的那个数。
问题得到完美解决。
这个看不明白，不一定是这个数吧。
[解决办法]
路过，顶！ 

 

查看更多 下一篇