劍指Offer:面試題40 數組中隻出現一次的數字

/*
數組中隻出現一次的數字:
一個整型數組裡除了兩個數字之外，其他的數字都出現了兩個，請寫程式找出這兩個隻出現一次的數字。要求時間
複雜度是O(n)，空間複雜度是O(1)

分析:
直接周遊，統計次數O(n),但空間複雜度為O(n)

書析:
a^a = 0，任何一個數字異或自己為0，是以從頭到尾依次異或數組中的每個數字，那麼最終結果恰好是那個隻出現
一次的數字。
試着把原數組分成兩個子數組，使得每個子數組包含一個隻出現一次的的數字，而其他數字都成對出現兩次。
我們從頭到尾異或，結果是兩個隻出現一次的數字的異或結果。異或的結果部位0，至少二進制表示中有一位為1，
在結果數字中找到第一個為1的位置，記為第n位。以第n位是不是1為标準把原數組中的數字分成兩個子數組，
第一個子數組中每個數字的第n位都是1，第二個子數組中每個數字的第n位都是0。是以出現了兩次的數字被
配置設定到同一個子數組中，于是我們把原數組分成了兩個子數組，每個子數組都包含一個隻出現一次的數字，而其他
數字都出現了兩次。
然後在分解後的數組中，從頭到尾異或，得到隻出現一次的數字。

假設輸入數組{2,4,3,6,3,2,5,5}。依次對數組中的每個數字做異或運算之後得到0010,。倒數第二位是1,來劃分
兩個數組{2,3,6,3,2}，{4,5,5}。
然後得到6,4
對于數字a，判斷從低位到高位第一次出現1的位置，累除2即可。(注意小于32位，整數，防止負數陷入死循環中)

輸入：
每個測試案例包括兩行：
第一行包含一個整數n，表示數組大小。2<=n <= 10^6。
第二行包含n個整數，表示數組元素，元素均為int。
輸出：
對應每個測試案例，輸出數組中隻出現一次的兩個數。輸出的數字從小到大的順序。
樣例輸入：
8
2 4 3 6 3 2 5 5
樣例輸出：
4 6
*/

/*
關鍵:
1 我們從頭到尾異或，結果是兩個隻出現一次的數字的異或結果。異或的結果部位0，至少二進制表示中有一位為1，
在結果數字中找到第一個為1的位置，記為第n位。以第n位是不是1為标準把原數組中的數字分成兩個子數組
a^a = 0，任何一個數字異或自己為0
2  while( ((num & 1) == 0) && (iIndex < 8*sizeof(int)) )//某數與1相與為0表明該數最低位為0,注意不能超過int的總位數，防止是負數陷入死循環
 {
  num = num >> 1;//向右表示除以2
3
*/

#include <stdio.h>
#include <string.h>
const int MAXSIZE = 1e6 + 1;
int _iArr[MAXSIZE];

int first1Bit(int num)//尋找一個數從低位到高位第一次出現1的位置
{
 int iIndex = 0;
 while( ((num & 1) == 0) && (iIndex < 8*sizeof(int)) )//某數與1相與為0表明該數最低位為0,注意不能超過int的總位數，防止是負數陷入死循環
 {
  num = num >> 1;//向右表示除以2
  iIndex++;
 }
 return iIndex;
}

bool isValid(int num,int iIndex)//判斷一個數的二進制位第n位是不是1，例如:2,0010,第1位是1，右移1位得001，若與0相與為1，即是
{
 for(int i = 1 ; i <= iIndex ; i++)//右移iIndex位
 {
  num = num >> 1;
 }
 if((num & 1) != 0)
 {
  return true;
 }
 else
 {
  return false;
 }
}

void appear1Times(int n)
{
 int iOr = 0;//設定異或初始值為0,O^a = a,0^a^a = 0
 for(int i = 0 ; i < n; i++)//剛開始，把整個數組先異或一遍
 {
  iOr = iOr ^ _iArr[i];
 }
 int iIndex = first1Bit(iOr);
 //接下來用最右邊的二進制1來将數組劃分為：兩個數組，每個數組中隻包含一個出現1次的數字，其餘出現的次數為兩次
 int iOr_1 = 0,iOr_0 = 0;
 for(int j = 0 ; j < n; j++)
 {
  if(isValid(_iArr[j],iIndex))
  {
   iOr_1 = iOr_1 ^ _iArr[j];
  }
  else
  {
   iOr_0 = iOr_0 ^ _iArr[j];
  }
 }
 if(iOr_1 < iOr_0)
 {
  printf("%d %d\n",iOr_1,iOr_0);
 }
 else
 {
  printf("%d %d\n",iOr_0,iOr_1);
 }
}

void process()
{
 int n;
 while(EOF != scanf("%d",&n))
 {
  if(n < 2 || n >= MAXSIZE)
  {
   continue;
  }
  memset(_iArr,0,sizeof(_iArr));
  for(int i = 0 ; i < n ; i++)
  {
   scanf("%d",&_iArr[i]);
  }
  appear1Times(n);
 }
}

int main(int argc,char* argv[])
{
 process();
 getchar();
 return 0;
}