剑指56-1 数组中数字出现的次数
2021-04-25 11:29
标签：result code 空间 要求 输入 整型 位运算 运用 pre 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例 1： 输入：nums = [4,1,4,6] 输入：nums = [1,2,10,4,1,4,3,3] 这个题可以先考虑，如果数组中只有一个数字出现了一次，其他都两次，怎么找到这个数？ 运用位运算，把所有数异或起来，因为重复出现的数都会抵消掉，最后剩下的就会是出现一次的数。 如果有两个数出现了一次，那么全部异或起来后，还是会有位为1，我们找到第一个为1的位（其实任何一位都可以，但是第一个花时间最少），这个位肯定是2个数不相同的一个位。 再遍历数组，根据这一位是否为1把数组分为两个子数组。重复的数肯定分到了一遍，两个单独的数肯定也是分到了两个数组中，这样在两个数组中分别寻找就可以了。 剑指56-1 数组中数字出现的次数 标签：result code 空间 要求 输入 整型 位运算 运用 pre 原文地址：https://www.cnblogs.com/rookiez/p/13258344.html
输出：[1,6] 或 [6,1]
示例 2：
输出：[2,10] 或 [10,2] 1 class Solution {
2 public:
3 vectorint> singleNumbers(vectorint>& nums) {
4 int len=nums.size();
5 if(!len)
6 return {};
7 int result=0;
8 for(auto it=nums.begin();it!=nums.end();it++){
9 result^=*it;
10 }
11 int pos=1;
12 while(result){
13 if(result&1)
14 break;
15 pos=pos1;
16 result=result>>1;
17 }
18 int num1=0,num2=0;
19 for(auto it=nums.begin();it!=nums.end();it++){
20 if((*it)&pos)
21 num1^=*it;
22 else
23 num2^=*it;
24 }
25 return {num1,num2};
26 }
27 };