找出数组中单独出现的三个数

男娘i 2022-05-18 04:55 232阅读 0赞

题目一：一个数组中，只有一个数字出现了一次，其余都是成对出现，找出这个数字  
题目二：一个数组中，有两个数字出现了一次，其余都是成对出现，找出这两个数字  
题目三：一个数组中，有三个数字出现了一次，其余都是成对出现，找出这三个数字

这三道题目是循序渐进的，典型的用异或求解的问题。

###### 1. 对于第一题，实际上比较简单，我们只需要将所有的数字全部异或一遍，就得到了 ######

代码比较简单，如下：

#include <stdio.h>
        int find_one(int *str, int sz)
        {
            int ret = 0;
            for (int i = 0; i < sz; i++)
            {
                ret ^= *(str + i);
            }
            return ret;
        }
    
        int main()
        {
            int arr[] = { 1,2,5,3,11,5,3,2,1 };
            int sz = sizeof(arr) / sizeof(arr[0]);
            int num1 = 0;
            int ret = find_one(arr, sz);
            printf("%d\n", ret);
            return 0;
        }

结果：11

###### 2.对于第二题，找出两个不同的数，假设这两个数为 a,b， ######

第一步：将数组中所有的数字都异或一遍，最终得到的结果记为c，则c=a^b，且 c ≠ 0，  
第二步：这就说明c的二进制中一定至少包含一个1，（我们取最低位的1）设 c 的二进制最低位为1的位置为pos，  
        则，a,b在pos位置上一定一个为0，一个为1，这就找出a和b的不同了，  
第三步：我们可以根据数组中所有数字在pos位置的不同来分组，pos位置为0的是一组，是1的是另一组，  
        这样a和b就被分开了，且分的两个组中其他元素也必成对出现（或为0），  
第四步：将分的两个组进行异或，即可得到a,b

代码如下：

#include <stdio.h>
    
        void find_two(int *str, int sz, int *px, int *py)
        {
            int ret = 0;
            int pos = 0;
            //将所有元素异或
            for (int i = 0; i < sz; i++)
            {
                ret ^= *(str + i);
            }
            //找出pos的位置（下面的代码pos表示右移的位数）
            for (int i = 0; i < 32; i++)
            {
                if (((ret >> i) & 1) == 1)
                {
                    pos = i;
                    break;
                }
            }
            //根据pos位置的元素来进行分组
            for (int i = 0; i < sz; i++)
            {
                if (((*(str + i) >> pos) & 1) == 1)
                {
                    *px ^= *(str + i);
                }
                else
                {
                    *py ^= *(str + i);
                }
            }
        }
    
        int main()
        {
            int arr[] = { 1,2,5,3,11,5,3,2,1,9 };
            int sz = sizeof(arr) / sizeof(arr[0]);
            int num1 = 0;
            int num2 = 0;
            find_two(arr, sz, &num1, &num2);
            printf("%d %d\n", num1, num2);
            return 0;
        }

结果：11 9  
注：上述代码中将num1和num2的地址传过去，是为了改变地址中的内容，函数就可以没有返回值了

###### 3. 第三个问题相对复杂一点点 ######

设三个不同的数字为a,b,c

第一步： 将数组所有的元素异或，得到结果ret，则ret = a^b^c，且 ret ≠ 0；  
         ret^a ≠ 0 ret^b ≠ 0 ret^c ≠ 0，证明：  
         ret^a 实际上就相当于b^c，因为b和c不相等，则ret^a不可能为0  
第二步： 写一个函数LastNumberOf1：只保留一个数字二进制的最后一位的1， 其余位为置0  
         则LastNumberOf1(ret ^ a)、LastNumberOf1(ret ^ b)、LastNumberOf1(ret ^ c)都不为0，  
         则LastNumberOf1(ret ^ a) ^ LastNumberOf1(ret ^ b) ^ LastNumberOf1(ret ^ c) ≠ 0  
第三步： 令N=LastNumberOf1(ret ^ a) ^ LastNumberOf1(ret ^ b) ^ LastNumberOf1(ret ^ c),设N最后一位为1的位置为pos  
         则在第pos位，LastNumberOf1(ret ^ a)、LastNumberOf1(ret^b)、LastNumberOf1(ret^c)一个为1,或者三个为1  
         如果三个都为1，那就说明ret在pos位一定与a,b,c在pos位的数字不同，且a,b,c在pos位置的数字一定相同  
         若a,b,c在pos位置都为0，0^0^0 = 0，矛盾  
         若a,b,c在pos位置都为1，1^1^1 = 1，矛盾  
         所有LastNumberOf1(ret ^ a)、LastNumberOf1(ret ^ b)、LastNumberOf1(ret ^ c)在pos位只有一个为1  
第四步： 这就找到了一个数字与另外两个数字的不同，LastNumberOf1(arr\[i\] ^ ret) 的最后一位1出现在第pos位的数中，  
         只有一个是单独出现的，其余成对出现 ，就能找出其中一个数  
第五步：当找出其中一个数字，只需在你创建一个数组，并将之前数组的内容都赋值进去，最后再加上之前找到的数字，  
        这个问题就又转换为找一个数组中两个不同的数

代码如下：

#include <stdio.h>
    
        int lastBitOf1(int num)
        {
            return num & ~(num - 1);
        }
    
        void find_three(int *str, int sz, int *px, int *py, int *pz)
        {
            int ret = 0;
            int pos = 0;
            int arr1[12] = { 0 };
            int flag = 0;
            for (int i = 0; i < sz; i++)
            {
                ret ^= *(str + i);
                arr1[i] = *(str + i);
            }
            for (int i = 0; i < sz; i++) 
            {
                flag ^= lastBitOf1(ret ^ *(str + i));
            }
            for (int i = 0; i < sz; i++) {
                if (lastBitOf1(*(str + i) ^ ret) == flag)
                    *px ^= *(str + i);
            }
            arr1[sz] = *px;
            ret ^= *px;
            for (int i = 0; i < 32; i++)
            {
                if (((ret >> i) & 1) == 1)
                {
                    pos = i;
                    break;
                }
            }
            for (int i = 0; i < sz + 1; i++)
            {
                if (((arr1[i] >> pos) & 1) == 1)
                {
                    *py ^= arr1[i];
                }
                else
                {
                    *pz ^= arr1[i];
                }
            }
        }
    
        int main()
        {
            int arr[] = { 1,2,5,3,11,10,5,3,2,1,9 };
            int sz = sizeof(arr) / sizeof(arr[0]);
            int num1 = 0;
            int num2 = 0;
            int num3 = 0;
            find_three(arr, sz, &num1, &num2, &num3);
            printf("%d %d %d\n", num1, num2, num3);
            return 0;
        }

结果：10 11 9