SingleNumberIII [source code]

public class SingleNumberIII {
static
/******************************************************************************/
public class Solution {
    public int[] singleNumber(int[] nums) {
        int diff = 0;
        for (int num : nums)
            diff ^= num;
        diff &= -diff;
        int num1 = 0, num2 = 0;
        for (int num : nums)
            if ((diff & num) == 0)
                num1 ^= num;
            else
                num2 ^= num;
        return new int[]{num1, num2};
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SingleNumberIII.Solution tester = new SingleNumberIII.Solution();
    }
}

这个算法的要求是O(N)的时间和O(1)的空间. 一上来就找这个目标怼可能有点难; 先想笨办法: 肯定就是做一个counts array; 这一题没有index domain equals value domain的条件, 所以直接InPlace做counts好像有点难;

没思路, 看答案了;

注意一个小的要点:

(diff & num) == 0

这里的这个括号不能省, bit操作符的优先级非常低;

最后的速度是1ms (79%). 这个题目不会做, 就算是看答案都花了一个多小时, 何况这一题的答案其实还算是比较简单的. 所以以后真的是, 一点思路都没有的问题就不要浪费太多时间了;

discussion上面一个贼聪明的解法:

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

1. 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).
2. 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.

public class Solution {  
    public int[] singleNumber(int[] nums) {  
        // Pass 1 :   
        // Get the XOR of the two numbers we need to find  
        int diff = 0;  
        for (int num : nums) {  
            diff ^= num;  
        }  
        // Get its last set bit  
        diff &= -diff;  

        // Pass 2 :  
        int[] rets = {0, 0}; // this array 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;  
    }  
}

这里get last set bit的方法也是很elegant, 来自Stefan; 可以记忆一下(reminder, 以前是有一个unset the last set bit的问题的, 还记得怎么写来的吗?);

自己想要验证的时候, 好像记不得负数的bit表示怎么求来的? 其实大概记得一个东西就行了:

-A = ~A + 1  
~A = -A - 1

不过好像真正想的时候他们用的其实是diff &= ~(diff - 1), 这个其实就很好理解了, 为了找到diff的最右边的一个1, 我们直接给diff-1, 这样, 假设diff本来的个位不是1, 那么这个最后的结果就导致最右边的10直接变成了01(after -1), 然后我们给这个结果再~一下, 那么这个01又变成10了, 这个10和原来的10进行&就会保留这个1;

如果diff原来的个位是1, 其实也很好证明; 略;

I think using the rightmost 1-bit is just for ease of coding (diff &= -diff will leave the rightmost 1-bit). In fact, you can use any 1-bit. This 1-bit implies that the two single numbers are different at this bit. Then we use this bit to split all the remaining numbers into two groups. Suppose the two single numbers are a and b and they differ in the third bit (a is 1 at this bit while b is 0). After splitting, numbers with 1 in the third bit will fall in the group of a while the remaining ones fall in the group of b. Till now, we will be able to get a and b via a simple within-group xor.

这个解释也是没毛病的, 确实是选任何一个都差不多, 但是find rightmost 1bit这个可能是比较熟悉比较好做了;

最后这个2pass的xor其实用的也是非常聪明:

The reason why XOR works is, to separate the 2 unique numbers, their bits will differ in atleast one position, which would be the 1's in XOR. We take the rightmost such 1 from the XOR. This 1 must have come from either numbers, to identify which, we XOR all numbers into 2 sets, one set which had that bit set and one which didn't. In the end, the duplicate numbers will cancel themselves out leaving only the unique numbers in each set.

另外这里在2pass的时候的check bit的操作(用&), 这个其实也是我的知识盲点;

这里的grouping其实也有一点小技巧, 你不用真的做这个group, 反正你group完了也是用来xor的, 所以干脆当判断一个num适合某一个group之后, 直接就xor到一个buffer里面就行了;

这个题目还是挺难的, 这个是discussion里面其他人的complaint:

I admit that if you see problem backward when you know the solution, then you will say: oh, of course we should care about that there must exist one bit that appears odd number of times!
But you simply don't know the above statement when you see the problem forward.

也就是说还有其他的办法? 这个把所有的数全都用bit来表示, 然后直接对32个bit位进行分析的思路, 以前有一个题目好像见过一次. 我思考这个问题的时候也往这个方向想了一下, 不过并没有想到什么好的办法; 不过听这里的这个意思, 估计还有另外一个思路来解这个题目?

另外我看到这个问题的时候还是太不敢尝试了. 这个bit展开的思路我也大概想到了, 借鉴以前的解法的思路我也想到了(也就是复用执勤single number I的xor解法), 但是就是不够坚定, 没有在这两个思路上花更多的时间;

这个是我在帖子下面给出的解释:

Why diff &= ~(diff - 1)

First, this the original formula to get the last set bit. The diff &= -diff is just an abbreviation with the knowledge of ~(diff - 1) = - (diff - 1) - 1 = -diff.

• If diff is set on the least significant bit, then this is trivially provable: the least significant bit is the last set bit. After the -1 operation, this least significant bit became 0, and is the only change to all bits of diff. Then we ~ the result, which means the least significant bit gets reverted to 1, while all the other bits are guaranteed to have been reverted. Thus the least significant bit is the only bit that is left unchanged and that could survive the & operation.
• If diff is unset on the least significant bit: let's focus on the rightmost occurrence of 10 in diff. The 1 bit in this 10 is the last set bit of diff. After -1 operation, this 10 becomes 01. All the 0 bits to the right of this rightmost 10 are all change to 1 bits, and all the other whatever bits to the left of this rightmost 10 would be remain unchanged:

**..**10_00..00  
after -1:  
**..**01_11..11

Then we do ~ operation. The **..** part would all be reverted, and none of them would survive the upcoming & operation. 01 would become back 10, and would both survive the & operation, although the bit 1 is the only one we care about. All those 11..11 part gets reverted back to 00..00 after the ~ operation, and does not matter to the & operation. Thus the only thing surviving the & operation would be the rightmost 10, or the last set bit which is within it.

Incidentally, it does not really matter which bit we choose for the second pass to succeed, but since there is an elegant way to find the rightmost set bit, then let's use that.

另外:

I think the standard way of finding the LSB (least significant bit) is x & (-x), which I learned from binary indexed tree (fenwick tree).

所以这个东西其实是一个梗; 不过能够理解其实是更好的;

另外, 其实JAVA本身有一个API:

diff = Integer.highestOneBit(diff);

所以这个直接就是可以找到一个1bit的, 虽然这个找到的不是last, 但是前面也说过了, 任何一个1bit都是可以的;

这个题目基本就这样了, discussion也没有其他更好的答案了;

Problem 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.

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?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Medium
Total Accepted:68K
Total Submissions:132.4K
Contributor: LeetCode
Related Topics
bit manipulation
Similar Questions
Single Number Single Number II