single number

题目描述：

一个数组中除了一个数出现p次外，其他每个数出现k次，p % k != 0，找出这个数。

算法分析：

bit manipulation

https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers

1. Given a non-empty array of integers, every element appears twice except for one. Find that single one.
   time complexity: O(n)
   space complexity: O(1)
   https://leetcode.com/problems/single-number/
   

   class Solution {
   public:
       int singleNumber(vector<int>& nums) {
           for(int i = 1; i < nums.size(); i++)
               nums[0] ^= nums[i];
           return nums[0];
       }
   };

2. Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
   time complexity: O(n)
   space complexity: O(1)
   https://leetcode.com/problems/single-number-ii/
   

   class Solution {
   public:
       int singleNumber(vector<int>& nums) {
           int x1 = 0, x2 = 0, mask = 0;
           for(int i : nums){
               x2 ^= x1 & i;
               x1 ^= i;
               mask = ~(x1 & x2);
               x2 &= mask;
               x1 &= mask;
           }
           return x1;
       }
   };

   
   每一步循环时输出相应x1,x2,和mask的值：

   #include <iostream>
   #include <string>
   #include <sstream>
   #include <algorithm>
   #include <vector>
   #include <bitset>
   using namespace std;
   
   int single(vector<int> nums){
       int x1 = 0, x2 = 0, mask = 0;
       for(int i : nums){
           x2 ^= x1 & i;
           x1 ^= i;
           mask = ~(x1 & x2);
           x2 &= mask;
           x1 &= mask;
           cout << i << ":" << endl;
           cout << "mask :" << bitset<4>(mask) << endl;
           cout << "x2: " << bitset<4>(x2) << endl;
           cout << "x1: " << bitset<4>(x1) << endl;
           cout << endl;
       }
       return x1;
   } 
   
   int main(){
       vector<int> nums = {2, 2, 3, 2};
       int res = single(nums);
       cout << "single number: "<< res << endl;
       return 0;
   } 

   
   输出：
   

   可以发现，x2的i-th bit和x1的i-th bit构成一个counter，来计数数组中数字i-th bit 出现1的次数，每次达到k，就将其置为0，将p表示为二进制数，若i-th bit不为0，则xi就为那个只出现一次的数字，证明在上述链接中。
   
   
3. 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.
   time complexity: O(n)
   space complexity: O(1)
   https://leetcode.com/problems/single-number-iii/
   

   class Solution
   {
   public:
       vector<int> singleNumber(vector<int>& nums) 
       {
           // Pass 1 : 
           // Get the XOR of the two numbers we need to find
           int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
           // Get its last set bit
           diff &= -diff;
   
           // Pass 2 :
           vector<int> rets = {0, 0}; // this vector stores the two numbers we will return
           for (int num : nums)
           {
               if ((num & diff) == 0) // the bit is not set
               {
                   rets[0] ^= num;
               }
               else // the bit is set
               {
                   rets[1] ^= num;
               }
           }
           return rets;
       }
   };