LeetCode 260 Single Number III 数组中除了两个数外，其他的数都出现了两次，找出这两个只出现一次的数...

84 阅读 0 评论 56 点赞

我是靠谱客的博主无辜自行车，最近开发中收集的这篇文章主要介绍LeetCode 260 Single Number III 数组中除了两个数外，其他的数都出现了两次，找出这两个只出现一次的数...，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements
appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
1.The order of the result is not important. So in the above example, [5, 3] is also correct.
2.Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

方法一：

首先计算nums数组中所有数字的异或，记为xor
令lowbit = xor & -xor，lowbit的含义为xor从低位向高位，第一个非0位所对应的数字
例如假设xor = 6（二进制：0110），则-xor为（二进制：1010，-6的补码）
则lowbit = 2（二进制：0010）

 1 class Solution {
 2 public:
 3     vector<int> singleNumber(vector<int>& nums) {
 4         int size=nums.size();
 5         if(size==0||nums.empty())
 6             return vector<int>();
 7         int diff=0;
 8         for(auto &ele:nums)
 9             diff^=ele;
10         vector<int> res(2,0);
11         diff&=-diff;//从低位向高位，第一个非0位所对应的数字
12         for(auto &ele:nums)
13             if(diff&ele)
14                 res[0]^=ele;
15             else
16                 res[1]^=ele;
17         return res;
18     }
19 };

方法二：

 1 class Solution {
 2 public:
 3     vector<int> singleNumber(vector<int>& nums) {
 4         int size=nums.size();
 5         if(size==0||nums.empty())
 6             return vector<int>();
 7         int sum=0;
 8         for(auto &ele:nums)
 9             sum^=ele;
10         vector<int> res(2,0);
11         //从低位向高位，第一个非0位所对应的数字
12         int n=1;
13         while((sum&n)==0)
14             n=n<<1;
15         for(auto &ele:nums)
16             if(n&ele)
17                 res[0]^=ele;
18             else
19                 res[1]^=ele;
20         return res;
21     }
22 };