260只出现一次的数字 III

tech2022-10-14  94

题目描述: 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 : 输入: [1,2,1,3,2,5] 输出: [3,5]

注意: 结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

方法1: 主要思路: (1)相对整个数组中的所有的元素进行一遍异或,获得的值是两个元素的异或结果; (2)从这个异或结果中,选出其二进制中为1的某一位,作为分割标志,将数组元素分成两组,则两个元素会分别分配到两个数组中,每组再单独进行异或,即可在两组中各自获得单独的元素;

class Solution { public: vector<int> singleNumber(vector<int>& nums) { int lable=0; //对数组进行整体的异或 for(int& num:nums){ lable^=num; } int split=1;//找到分割的位 while(true){ if(lable&split){ break; } split<<=1; } int res1=0; int res2=0; //将数组分成两组,分别进行异或 for(int&num:nums){ if(num&split){//分割标识 res1^=num; } else{ res2^=num; } } return {res1,res2}; } };
最新回复(0)