leetcode打卡

前几天记录了一小段关于异或的笔记,发现自己对于异或(或者说是位运算)的理解还是太过于浅薄了.

今天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]

 解法:异或分组求解

数组中存在两个只出现了一次的数字,全组异或得到的结果是两个数字异或的结果

找到结果中第一位是1的位置,根据这个位置进行分组,必然可以将两个只出现了一次的数字分成两组,相同数字在同一位也相同,可以分配在同一组.

依靠k=1不断左移试出第一位为1  的位置.

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int res=0;
        for(int i=0;i<nums.size();++i)
        res^=nums[i];//对vector容器的所有数字异或得到两个只出现一次数字的结果
        int k=1;//令k=1,方便之后对于res结果的判定,找出res以二进制第一个不为0的位置.
        while((k&res)==0)
        {
            k<<=1;//k=1以二进制来右移得到res第一个不为0的位置
        }
        int a=0,b=0;
        for(int i=0;i<nums.size();++i){
            if((k&nums[i])==0)a^=nums[i];//根据k和nums[i]的与运算进行分组运算得到两组数据
            else b^=nums[i];//将两个只出现一次的数字分成两个不同的组,然后分别异或得到两个数字
        }
       return vector<int>{a,b};//返回a,b
    }
};

foreach循环属于特殊简化的for循环,为了提升开发速度而设计的语句.

for(int i:nums){
cout<<i<<endl;}

 nums可以是数组类型集合类型,枚举类型或者是vector类型,nums存在多少个数字,就循环多少次,每一次循环nums就取一个值交给i,i相当于一个接收器,接收nums给的值,每一次循环都重新赋值.

但是一定要注意i与nums必须是相同的类型,如下就会报错.

for(int i:str){}

str是字符串数组,但是i却是int类型,所以i作为接收器就无法成功接收到str类型的值.