[Leetcode] Single Number III, Solution
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.nums = [1, 2, 1, 3, 2, 5]
, return[3, 5]
.[5, 3]
is also correct.1: class Solution {
2: public:
3: vector<int> singleNumber(vector<int>& nums) {
4: int length = nums.size();
5: // get the xor result of the array, b ^ c
6: int xor_result = 0;
7: for(int i =0; i< length; i++) {
8: xor_result ^= nums[i];
9: }
10: // get the K of first bit, which equals 1
11: int first_one_index = 0;
12: for(first_one_index =0; first_one_index< 32; first_one_index++) {
13: if((xor_result>>first_one_index) & 1 == 1) {
14: break;
15: }
16: }
17: // use k to split the array into two part
18: // xor the sub array, if the element's Kth bit also equals 1, b
19: int xor_twice = 0;
20: for(int i =0; i< length; i++) {
21: if((nums[i]>>first_one_index) & 1 == 1) {
22: xor_twice ^= nums[i];
23: }
24: }
25: // with b, easy to get c by math
26: vector<int> result = {xor_twice, xor_result ^ xor_twice };
27: return result;
28: }
29: };