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
与single number1 类似 每个重复的数都出现两次, 假设不重复的数字为a, b. 用^遍历所有数组就会得到一个a^b的结果c. 我们知道在c中, 每一位1说明在这一位上a与b是不同的. nums = [1, 2, 1, 3, 2, 5]
, return [3, 5]
.3 (0011) xor
5 (0101)=
6 (0110)
我们只需要找到这1位, 然后把数组按照这一位是1还是这一位是0分为两个数组 然后分别做^遍历 就会在每个组中找到一个独立的单身狗了.
public class Solution { public int[] singleNumber(int[] nums) { int[] res = new int[2]; if (nums == null || nums.length == 0) { return res; } int tem = 0; for (int c : nums) { tem ^= c; } int pre = 0; while (tem!= 0) { pre = tem; tem &= tem - 1; } for (int n : nums) { if ((n & pre) == 0) { res[0] ^= n; } else { res[1] ^= n; } } return res; } }
没有评论:
发表评论