九度OJ 1351：数组中只出现一次的数字（位运算）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：3098

解决：906

题目描述：: 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

输入：: 每个测试案例包括两行：

第一行包含一个整数n，表示数组大小。2<=n <= 10^6。

第二行包含n个整数，表示数组元素，元素均为int。

输出：: 对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。

样例输入：

8

2 4 3 6 3 2 5 5

样例输出：

4 6

思路：

这个题的简单版本是数组里除了一个数之外，其他数都出现了两次，求唯一不同的数。

简单版本的做法是：所有数进行异或操作，最终结果就是这个唯一的数。

对于这个题，仍可利用异或运算的性质来做。方法是：

对所有数进行异或，得到的结果就是两个不同数的异或值X。由于这两个数不同，X的二进制中必定有一位是1，假设仅仅这个位上是1的二进制数为M。

再对所有数按照与M为0或1进行分类，分别异或得到的最终值就是所求的两个不同数。

代码：

#include <stdio.h>

#define N 1000000

int main(void)

{

    int n, i;

    int a[N];

    int m, k1, k2;

    while (scanf("%d", &n) != EOF)

    {

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

            scanf("%d", &a[i]);

        k1 = 0;

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

            k1 ^= a[i];

        m = 1;

        while ((k1&m) == 0)

            m <<= 1;

        k1 = k2 = 0;

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

        {

            if (((a[i])&m) == 0)

                k1 ^= a[i];

            else

                k2 ^= a[i];

        }

        if (k1 < k2)

            printf("%d %d\n", k1, k2);

        else

            printf("%d %d\n", k2, k1);

    }

    return 0;

}

/**************************************************************

    Problem: 1351

    User: liangrx06

    Language: C

    Result: Accepted

    Time:790 ms

    Memory:4748 kb

****************************************************************/

巴特西

九度OJ 1351：数组中只出现一次的数字（位运算）

最新文章

热门文章

巴特西

九度OJ 1351：数组中只出现一次的数字 （位运算）

最新文章

热门文章

九度OJ 1351：数组中只出现一次的数字（位运算）