一个常见问题的推广

你可能之前碰到过下面这些问题：

1. 有n个数，其中一个出现1次，另外的数出现2次，求出现1次的那个数。

2. 有n个数，其中一个出现1次，另外的数出现3次，求出现3次的那个数。

3. 有n个数，其中一个出现2次，另外的数出现4次，求出现2次的那个数。

要求时间复杂度O(n)，空间复杂度O(1)

你应该知道第1个问题可以用异或轻松解决：将n个数作异或，剩下的那个数即为所求。

另外的两个问题就有点棘手，不是那么容易解决的。不妨再将这个问题一般化：有n个数，其中一个出现x次，另外的数出现y次，求出现x次的那个数。（通常x<y）

这个问题有一个通用的算法：将每个数写成二进制表达，对每位做加法，然后模y，则结果要么是0，要么是x。如果是0，说明所找的数在该二进制位上为0，否则为1。对所有的n个数循环32遍，即可得到所找的数。时间复杂度为O(n)，空间复杂度O(1)，满足要求。

其实，还可以对这种方法作一点改进，只需要一步循环：考虑数组m[y]，其中m[i]的二进制表达中为1的位表示在n个数在这些位上的和加起来模y的结果是i。初始化是m[0]的所有位都是1，其它m[i]都是0，之后对n个数循环，每次更新m[i]时，需要用到上一次的m[i-1]的结果，具体看代码：

int f(const int *a, int n, int y, int x)  // usually x < y

{

    unsigned int m[y] = {-1, 0, 0, ... };   // change this in actual code

    unsigned int mb;

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

        mb = m[y-1];

        for (int j = y-1; j > 0; --j)

            m[j] = (m[j] & ~a[i]) | (m[j-1] & a[i]);

        m[0] = (m[0] & ~a[i]) | (mb & a[i]);

    }

    return m[x];

}

其中，m[j] = (m[j] & ~a[i]) | (m[j-1] & a[i])这句最关键，解释如下：当遍历到第i个数后，m[j]的第k位是1有两种可能：要么遍历第i个数之前m[j]的第k位就是1，同时第i个数的第k位为0，也即(m[j] & ~a[i])；或者是遍历前m[j-1]的第k位是1，同时第i个数的第k位为1，相加后即可得m[j]的第k位为1，也即(m[j-1] & a[i])。同时，由于计算m[j]需要用到上次m[j-1]的结果，计算m[0]需要用到上次m[y-1]的结果，所以从y-1遍历到0比较方便。

如果想明白了这个问题，那么以后碰到类似的问题就可以直接给出终极解决方案了，世界从此清静了。。。。。。