LeetCode 4月28每日一题 面试题56 - I. 数组中数字出现的次数 LeetCode

问题描述:

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

解题思路:

若不考虑时间空间复杂度,建立map键值对,统计字符个数,如下:

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        map<int,int> m;
        //统计个数
        for(int i=0;i<nums.size();i++){
            m[nums[i]]++;
        }
        vector<int> res;
        //遍历查找
        map<int, int>::iterator iter;
        for(iter = m.begin(); iter != m.end(); iter++) {
            if(iter->second==1) res.push_back(iter->first);
        }
        return res;
    }
};

可是题目要求,时间复杂度O(n),空间复杂度O(1)

于是上面的思路不行,转换思路,这题其实我最开始写的时候只有一半思路

就是使用^运算符,异或运算符,是相同取0,不同取1

例如

A = 0011 1100

B = 0000 1101

A^B = 0011 0001

同时还有与&,或|运算符

A&B = 0000 1100

A|B = 0011 1101

假设问题1:

如果数组中只存在一个单独出现一次的元素,其他元素都出现俩次,nums={a,a1,a1,...,an,an},类似这种形式,求出现一次的元素值

数组中的全部元素进行异或运算

res = a^a1^a1^...^an^an 

已知ai^ai=0 则res = a即为出现一次的元素

此问题就是LeetCode 136题,感兴趣的可以看看LeetCode 136

但是题意已给出数组中,只有俩个数字出现一次,其余都出现了俩次,nums={a,a1,a1,b,...,an,an}就是这种形式

首先将数组中的全部元素进行异或运算

res = a^a1^a1^b^...^an^an

已知ai^ai=0,则res=a^b,则我们已经求出res为俩个单独元素的异或值

当时做到这里,我就卡壳了,后来看了大神的解法

既然a,b 不一样,那么res肯定不是0,那么res的二进制肯定至少有1位(第n位)是1,只有0^1才等于1

所以a,b 在第n位,要么a是0,b是1 ,要么b是0,a是1

A = 0011 1100

B = 0000 1101

A^B = 0011 0001  如此例子,B在第一位是1,A在第一位是0。

在计算机中 数字都是以补码形式存在,正数补码等于自己,负数的补码等于反码+1,反码是符号位不变,其他位取反

s = 3 ^ 5; 0011 ^ 0101 = 0110 = 6假设int是8位

-6  原码1000 0110

反码1111 1001

补码1111 1010

下面的建议大家牢记,除非你对计算机基础掌握很熟练

s&(-s) = 0000 0010

令k = s&(-s),则k就是就是保留s的最后一个1(从右往左),并且将其他位变为0  也就是s最后一个1是倒数第二位

k&3 = 0010,k&5=0000

此时我们就可以用k来区分俩个单独数字,这个时候我们考虑数组里面其他成对出现的元素,

值分为俩类,k&a=0 或者 k&a!=0

到这里大家就发现了,使用k将此问题分解为俩个上面所描述的问题1,具体代码如下:

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int ans = 0;
        for(int i=0;i<nums.size();i++){
            ans = ans^nums[i];
        }
        int k = (-ans)&ans;
        vector<int> res(2,0);
        for(int i=0;i<nums.size();i++){
            if(k&nums[i]){
                res[0]=res[0]^nums[i];
            }else{
                res[1]=res[1]^nums[i];
            }
        }
        return res;
        
    }
};

 

 

 

上一篇:elasticesearch搜索返回高亮关键字


下一篇:面试题56-I:数组中数字出现的次数(C++)