260. Single Number III.md

title	toc	date	tags	top
260. Single Number III	false	2017-08-17	Leetcode Bit Manipulation	260

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:

Input:  [1,2,1,3,2,5]
Output: [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非常类似。不同的是，前者仅有一个只出现一次的数字，这里有两个只出现一次的数字。

一个解决方法是将数组分成两部分，每一部分包含且仅包含一个只出现一次的数字$a,b$。数组中所有数的按位异或($\land$)，的结果相当于$a,b$的异或$a\land b$。由于$a,b$肯定不同(如果相同，则出现两次)，所以数组按位异或结果的二进制位表示中肯定有1(不同的数字异或结果为1，相同的数字异或结果为0)。找到任意一个1的位置$sn$，也就是$a,b$的二进制表示中有差异的位置。如果将$sn$与$a,b$按位与，它们的结果肯定不同，即完成了分类。

public int[] singleNumber(int[] nums) {
    if (nums == null || nums.length < 2)
        throw new IllegalArgumentException();
    // 得到异或结果
    int sn = 0;
    for (int num : nums)
        sn ^= num;
    
    // 除了异或结果的最低位1，其他都设置为0
    sn = sn & (-sn);
    
    // 分类
    int digitOne = 0, digitTwo = 0;
    for (int num : nums)
        if ((sn & num) == 0) digitOne ^= num;
        else digitTwo ^= num;
    return new int[]{digitOne, digitTwo};
}