260. Single Number III

  • 49.9%

https://leetcode.com/problems/single-number-iii/?tab=Description

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.

1
2
3
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?

剑指offer 40

方法一:

求第一位非0, diff &= -diff.

-diff求的相反的数字,存储是补码, 取反加1.

diff = 110

diff & (-diff) = 010

https://discuss.leetcode.com/topic/21605/accepted-c-java-o-n-time-o-1-space-easy-solution-with-detail-explanations

Accepted C++/Java O(n)-time O(1)-space Easy Solution with Detail Explanations

Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

  • In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value ‘1’) in the XOR result. Find out an arbitrary set bit (for example, the rightmost set bit).
  • In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementinoed bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group.

Complexity:

  • Time: O (n)
  • Space: O (1)

A Corner Case:

  • When diff == numeric_limits::min(), -diff is also numeric_limits::min(). Therefore, the value of diff after executing diff &= -diff is still numeric_limits::min(). The answer is still correct.
    C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution
{
public:
vector<int> singleNumber(vector<int>& nums)
{
// Pass 1 :
// Get the XOR of the two numbers we need to find
int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
// Get its last set bit
diff &= -diff;

// Pass 2 :
vector<int> rets = {0, 0}; // this vector stores the two numbers we will return
for (int num : nums)
{
if ((num & diff) == 0) // the bit is not set
{
rets[0] ^= num;
}
else // the bit is set
{
rets[1] ^= num;
}
}
return rets;
}
};

我的代码实现:

注意用&还是用^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> res;
int flag = 0;
for(auto num:nums)
flag ^= num;
flag = flag&-flag;
int num1 = 0, num2 = 0;
for(auto num:nums){
if(num&flag)
num1 ^= num;
else
num2 ^= num;
}
res.push_back(num1);
res.push_back(num2);
return res;
}
};

Thanks for reading :)

Acknowledgements:

  • Thank @jianchao.li.fighter for introducing this problem and for your encouragement.
  • Thank @StefanPochmann for your valuable suggestions and comments. Your idea of diff &= -diff is very elegent! And yes, it does not need to XOR for both group in the second pass. XOR for one group suffices. I revise my code accordingly.
  • Thank @Nakagawa_Kanon for posting this question and presenting the same idea in a previous thread (prior to this thread).
  • Thank @caijun for providing an interesting test case.

方法二:

int lastBit = (aXorb & (aXorb - 1)) ^ aXorb;

https://discuss.leetcode.com/topic/21984/c-solution-o-n-time-and-o-1-space-easy-understaning-with-simple-explanation

C++ solution O(n) time and O(1) space, easy-understaning with simple explanation

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> singleNumber(vector<int>& nums) {
int aXorb = 0; // the result of a xor b;
for (auto item : nums) aXorb ^= item;
int lastBit = (aXorb & (aXorb - 1)) ^ aXorb; // the last bit that a diffs b
int intA = 0, intB = 0;
for (auto item : nums) {
// based on the last bit, group the items into groupA(include a) and groupB
if (item & lastBit) intA = intA ^ item;
else intB = intB ^ item;
}
return vector<int>{intA, intB};
}

https://discuss.leetcode.com/topic/25382/sharing-explanation-of-the-solution

Sharing explanation of the solution

If you were stuck by this problem, it’s easy to find a solution in the discussion. However, usually, the solution lacks some explanations.

I’m sharing my understanding here:

The two numbers that appear only once must differ at some bit, this is how we can distinguish between them. Otherwise, they will be one of the duplicate numbers.

One important point is that by XORing all the numbers, we actually get the XOR of the two target numbers (because XORing two duplicate numbers always results in 0). Consider the XOR result of the two target numbers; if some bit of the XOR result is 1, it means that the two target numbers differ at that location.

Let’s say the at the ith bit, the two desired numbers differ from each other. which means one number has bit i equaling: 0, the other number has bit i equaling 1.

Thus, all the numbers can be partitioned into two groups according to their bits at location i.
the first group consists of all numbers whose bits at i is 0.
the second group consists of all numbers whose bits at i is 1.

Notice that, if a duplicate number has bit i as 0, then, two copies of it will belong to the first group. Similarly, if a duplicate number has bit i as 1, then, two copies of it will belong to the second group.

by XoRing all numbers in the first group, we can get the first number.

by XoRing all numbers in the second group, we can get the second number.


https://discuss.leetcode.com/topic/43805/bit-manipulation-beats-99-62

Bit manipulation beats 99.62%

Find the rightmost set bit, divide numbers into two groups. Each group will end up being one unique number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int[] singleNumber(int[] nums) {
int result[] = new int[2];
int xor = nums[0];
for (int i=1; i<nums.length; i++)
{
xor ^= nums[i];
}

int bit = xor & ~(xor-1);
int num1 = 0;
int num2 = 0;

for (int num : nums)
{
if ((num & bit) > 0)
{
num1 ^= num;
}
else
{
num2 ^= num;
}
}

result[0] = num1;
result[1] = num2;
return result;
}

https://discuss.leetcode.com/topic/34545/share-my-c-solution

Share my C++ solution,

  1. assume that A and B are the two elements which we want to find;
  2. use XOR for all elements,the result is : r = A^B,we just need to distinguish A from B next step;
  3. if we can find a bit ‘1’ in r,then the bit in corresponding position in A and B must be different.We can use {last = r & (~(r-1))} to get the last bit 1 int r;
  4. we use last to divide all numbers into two groups,then A and B must fall into the two distrinct groups.XOR elements in eash group,get the A and B.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int r = 0, n = nums.size(), i = 0, last = 0;
vector<int> ret(2, 0);

for (i = 0; i < n; ++i)
r ^= nums[i];

last = r & (~(r - 1));
for (i = 0; i < n; ++i)
{
if ((last & nums[i]) != 0)
ret[0] ^= nums[i];
else
ret[1] ^= nums[i];
}

return ret;
}
};

https://discuss.leetcode.com/topic/21883/my-java-solution-adapted-from-the-commonest-solution-here

My Java solution adapted from the commonest solution here

I read @zhiqing_xiao ‘s post to get an idea about the solution. His solution is really smart and elegant, but it took me a while to get understand how “diff &= -diff” works. I changed it a little bit to make it better understood, but it is totally based on his solution.

Instead of using the right-most “1” of diff, I used the left-most “1” to divide groups. This should also do the trick.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public int[] singleNumber(int[] nums) {
int diff = 0;
for(int num: nums){
diff^=num;
}
diff = Integer.highestOneBit(diff);

int[] result = new int[2];
Arrays.fill(result,0);
for(int num: nums){
if((diff & num) == 0){
result[0] ^= num;
}
else{
result[1] ^= num;
}
}
return result;
}
}
谢谢你,可爱的朋友。