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?

分析

这道题和leetcode-136-Single-Number不同的是，这里面有两个单身狗，仍然是位操作，如果能将两个单身狗分开，也就是说将所有元素分成两组，两组都是leetcode-136-Single-Number的情况，思路就简单了，怎么做呢？假设两个单身狗是a，b，将所有元素异或的结果即a，b异或的结果，这里记为c，通过c & ~(c-1)可以求得从左到右的第一个1，这个1怎么得到的？通过a，b异或得到的，自然可以通过这一位将a，b分开。

解决方案1(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
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xor_result = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            xor_result ^= nums[i];
        }
        
        int split_num = xor_result & ~(xor_result-1);
        
        int result1 = 0;
        int result2 = 0;
        
        for(int item: nums) {
            if(item & split_num) {
                result1 ^= item;
            }else {
                result2 ^= item;
            }
        }
        vector<int> result = {result1, result2};
        return result;
    }
};

相关问题

题目来源