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?
给一串数组,其中数字都是成对出现的,只有两个数字是单独的。
首先,对数组中所有数字以此做异或运算,这样,得到的结果为2个单独数字异或运算的结果。
其次,由于两个数字不相同,所以必至少有一位为1 。
再次,选择某一位为1的,将原数字以此为标准分成两个数组,这样两个单独的数字就会分到两个数组中,而其他相同成对出现的数字也不会分开
最后,两个分开的数组以此对所有元素做异或,最后得到的两个值就是原数组中两个单独出现的值。
C#代码:
public class Solution { public int[] SingleNumber(int[] nums) { int result = 0; for(int i = 0; i < nums.Count(); i++) { result ^= nums[i]; } int findOne = 1; while((result & findOne) == 0) { findOne = findOne << 1; } int[] returnResult = {0, 0}; for(int i = 0; i < nums.Count(); i++) { if ((findOne & nums[i]) == 0) { returnResult[0] ^= nums[i]; } else { returnResult[1] ^= nums[i]; } } //int[] returnResult = {result1, result2}; return returnResult; } }