经典位运算算法模板-附LeetCode剑指 Offer 56 - I. 数组中数字出现的次数-题解-python && C++源代码

剑指 Offer 56 - I. 数组中数字出现的次数

难度中等630收藏分享切换为英文接收动态反馈

一个整型数组 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

通过次数153,689提交次数221,806

解题思路: 

相同的数字异或为0,不同的数字异或为1,0异或任何数字为数字自身,本着这个原则,我们可以进行这道题的学习,

第一步:我们将整个数组的数都与0进行异或,我们就可以得到两个不同的数字,设为a , b,即a和b异或的值。

第二步:因为相同的数字异或为0,不同的数字异或为1,因此我们找到a和b异或值中第一个为1的位置m
第三步:我们将m与全数组的值进行与,构建两个子数组这样可以将两个不同的值a和b分在不同的数组,且相同的值与
m与的值一定相同,我们把他分在相同的组,将两个组的值进行异或,即可得到a和b的值。

Python代码:

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        a , m , x , y= 0 , 1 , 0 , 0  #相同的数字异或为0,0异或任何数字为数字自身
        for i in nums:a = a^i #数组全部异或,求出只出现两个数字的异或值
        while a&m==0 : m<<=1  #判断第一次出现1的地方
        for i in nums:#遍历数组
            if i&m: x ^= i#根据跟与m的情况,可以将 两个不同的值分到两个不同的组进行异或
            else: y ^= i#相同的值跟m与的情况一定是相同的,因此可以将相同的值分到同一组,不同的值分到不同的组
        return [x, y]
        

        

C++代码:

 

class Solution {
public:
    vector singleNumbers(vector& nums) {
        int a=0 , m=1 , x=0 , y=0;
        for(auto &i: nums) a ^= i;//遍历异或
        while ((a&m)==0) m <<= 1; //寻找第一个为1的地方m
        for(auto &j: nums){       
            if (j&m) x^=j;  //将数组分为两个子数组分别进行异或
            else y^=j;
        }
        return {x , y};


    }
};

你可能感兴趣的