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.

Example:

1
2
Input:  [1,2,1,3,2,5]
Output: [3,5]

这题真的很巧妙，本质上还是使用了single number的方法来做。

但是这里需要用方法把两个数字的区分开来，然后把所有数字分成两组，每组中有一个单独的数字，另外为成对出现的数字。

首先对所有的数字进行异或处理，可以得到了两个单独数字的异或值，这里为3和5的异或：ox=11\^101=110。我们可以看出，最能区分出两个数字的方法为异或值的最右边的一位1，该位上可以区分3和5。接着就可以用ox\^-ox的方法得到最低位的异或值为1的数字（因为-ox为ox去非后+1），这里就可以得到10。然后用10去与所有的值，可以成功将nums分成两类，每个单独的值在一类里，其余的值都是成对出现。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> result(2);
        int ox = 0;
        for (int i = 0; i < nums.size(); i++)
            ox ^= nums[i];

        ox &= -ox;

        for (int i = 0; i < nums.size(); i++) {
            if (ox&nums[i])
                result[0] ^= nums[i];
            else
                result[1] ^= nums[i];
        }
        return result;
    }
};