260. Single Number III
Leetcode Bit ManipulationGiven 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:
- 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?
分析¶
这道题目与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};
}