## Friday, October 16, 2015

### [Leetcode] Single Number III, Solution

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:
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?
[Thought]

^[A]   =  b^c ,  因为其他的数因为出现了两次，异或的过程中就被清零了。

[Code]
``````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:  };
``````

Git hub: https://github.com/codingtmd/leetcode/blob/master/src/Single_Number_III.cpp