Single Number III

Single Number III

---

首先，上周五没有更新，很是抱歉。因为周五的时候参加黑客马拉松，coding了24小时，实在是没有腾出时间来。我会把那天的题目补上的。

---

今天是一道位运算的题目，来自LeetCode，难度为Medium，Acceptance为39.4%。与之前的Single Number（回复008查看）是同一系列。

题目如下

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:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

解题思路及代码见阅读原文

回复0000查看更多题目

思路如下

首先，该题和Single Number同是位运算的题目。在Single Number一题中，将所有数字做异或运算就可以得到最后的结果。

然而，在本题中因为有两个不同的数字，只做异或是不能得出最后结果的。那么应该如何求呢？

其实，思路较为简单，既然有两个不同的数字，我们只需将所有数字按一定规则分为两组，然后分别做异或运算，就可得到两个不同的数，而这两个数就是最后的结果。那么应该按什么规则分组呢？

我们还是按照二进制的思路来思考，既然有两个数不同，那么从二进制的角度，这两个数一定有一个二进制位是不同的（即一个是0， 另一个是1）。那么就可以按照这个规则，将所有数字分成两组，之后按照上述思路就可以得到最后的结果。

代码如下

java版

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;
}