世界热点评！数组中找出只出现一次的两个数字

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

世界热点评！数组中找出只出现一次的两个数字

2023-02-14 10:58:20 来源：博客园

(资料图片)

问题：剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode）

该问题巧妙地利用了异或运算的性质，两个相同的数字相异或为0，遍历完所有的数字后，只剩下两个不相同的数字的异或值，n = x^y；

再利用 n为1的首位，计算出这个值，将其遍历数组，进行与运算，由其结果为0或1 ，得到两个数组；

对两个数组进行分别遍历异或，最后得到的值即为只出现一次的值

时间复杂度：O(N);空间复杂度：O(1);

class Solution {public:    vector singleNumbers(vector& nums) {        int n = 0x0;        for(auto num:nums){            n ^= num;//遍历异或所有数字；        }        int m = 0x1;        while((n & m) == 0){            m <<= 1;//找到首位为1的位，此位代表两个数字值不相同的位        }        int x=0,y=0;        for(auto num : nums){            if(m & num) x ^= num;            else y ^= num;        }        return vector {x,y};    }};

其中，找出首位为1的值m 可以简化代码为：

m = n & (~n +1)

或者

m = n -(n & (n -1))

关键词：空间复杂度时间复杂度