数组中数字出现的次数-剑指 Offer 56 - I（数组+【排序查找|分组异或】+c）

喜欢ヅ旅行 2023-01-17 15:57 59阅读 0赞

题目描述：  
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = \[4,1,4,6\]  
输出：\[1,6\] 或 \[6,1\]  
示例 2：

输入：nums = \[1,2,10,4,1,4,3,3\]  
输出：\[2,10\] 或 \[10,2\]

限制：

2 <= nums.length <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解  
这道题目最容易想到的思路就是排序，然后比较相邻的元素是否相同就可以了，因为排序后只出现一次的元素与其相邻的元素是不同的。

但是该题的要求是时间复杂度为O(n)，我最初想到了转二进制使用异或，但是由于存在两个数只出现一次，所以异或后的结果实际等同于出现一次的两个数做异或的结果，那怎么去把这两个数分离出来呢，卡在了这。后面看了官方题解，官方提到了一个解决方法：**进行分组，将异或后某位不为0的位，按照该位为0或1分为两组，一组数据该位为0，另一组数据该位为1，此时相当于将两个出现一次的数据分别放到了两组中，然后再分别对每组做异或就可以了。**

这里记录下上述两种方法的实现：

第一种思路：排序加查找

int cmp(const void* a, const void* b)
    { 
        return *(int *)a - *(int *)b;
    }
    
    int* singleNumbers(int* nums, int numsSize, int* returnSize){ 
        *returnSize = 2;
        qsort(nums, numsSize, sizeof(int), cmp);
        int *res = (int *)malloc(sizeof(int) * 2);
        int flag = 0;
        for(int i = 0; i < numsSize - 1; i++)
        { 
            if(nums[i] != nums[i+1])
            { 
                res[flag++] = nums[i];
            }
            else
            { 
                i++;
            }
        }
        if(flag == 1) res[flag] = nums[numsSize-1];
        return res;
        
    }

第二种思路：分组异或  
逻辑运算符的使用，之前我会采取自己去转二进制数放到数组中，其实此处应用逻辑运算符，代码更加简洁，而且非常方便

int findFirst(int xorres)
    { 
        int index = 0;
        while((xorres & 1) == 0)  //找到右数第一位是1的位
        { 
            xorres >>= 1;
            index++;
        }
        return index;
    }
    int isbit1(int num, int index) //判断右数index位是否为1
    { 
        return ((num >> index) & 1);
    }
    int* singleNumbers(int* nums, int numsSize, int* returnSize){ 
        *returnSize = 2;
        int *res = (int *)malloc(sizeof(int) * 2);
        memset(res, 0, sizeof(int) * 2); //初始化，保证后面异或结果的正确性，0与任何数异或都为该数
    
        int xorres = 0; //异或之后的结果
    
        for(int i = 0; i < numsSize; i++){ 
            xorres ^= nums[i]; //对每个数字进行异或
        }
    
        int index = findFirst(xorres); //异或之后的二进制数肯定包含1，找到异或之后右数第一个为1的位，以此分组
    
        for(int i = 0; i < numsSize; i++)
        { 
            if(isbit1(nums[i], index)) res[0] ^= nums[i]; //右数第index位是1的为一组
            else res[1] ^= nums[i]; //右数第index位是0的为一组
        }
        return res;
    }