程序員面試題精選100題(63)-數組中三個只出現一次的數字

時間:2019-09-22 編輯:范文亭
程序員面試題精選100題(63)-數組中三個只出現一次的數字

       在將這個題目之前,先講講一個數組中有兩個數字出現一次,其他的都出現兩次的情況。具體題目如下:

     題目:一個整型數組里除了兩個數字之外,其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間復雜度是O(n),空間復雜度是O(1)。

分析:首先考慮這個問題的一個簡單版本:一個數組里除了一個數字之外,其他的數字都出現了兩次。請寫程序找出這個只出現一次的數字。這個題目的突破口在哪里?題目為什么要強調有一個數字出現一次,其他的出現兩次?想到了異或運算的性質:任何一個數字異或它自己都等于0。也就是說,如果從頭到尾依次異或數組中的每一個數字,那么最終的結果剛好是那個只出現一次的數字,因為那些出現兩次的數字全部在異或中抵消掉了。

有了上面簡單問題的解決方案之后,回到原始的問題。如果能夠把原數組分為兩個子數組,在每個子數組中,包含一個只出現一次的數字,而其他數字都出現兩次。如果能夠這樣拆分原數組,按照前面的辦法就是分別求出這兩個只出現一次的數字了。

還是從頭到尾依次異或數組中的每一個數字,那么最終得到的結果就是兩個只出現一次的數字的異或結果。因為其他數字都出現了兩次,在異或中全部抵消掉了。由于這兩個數字肯定不一樣,那么這個異或結果肯定不為0,也就是說在這個結果數字的二進制表示中至少就有一位為1。在結果數字中找到第一個為1的位的位置,記為第N位。現在以第N位是不是1為標準把原數組中的數字分成兩個子數組,第一個子數組中每個數字的第N位都為1,而第二個子數組的每個數字的第N位都為0。

現在已經把原數組分成了兩個子數組,每個子數組都包含一個只出現一次的數字,而其他數字都出現了兩次。因此到此為止,所有的問題都已經解決。

測試代碼如下:

#include<iostream>
using namespace std;

unsigned int FindFirstBitIs1(int num)
{
  int indexBit=0;
  while(((num&1)==0) &&(indexBit<32))
  {
    num=num>>1;
++indexBit;
  }
  return indexBit;
}

bool IsBit1(int num,unsigned int indexBit)
{
  num=num>>indexBit;
  return (num&1);
}

void FindNumsAppearOnce(int data[],int length,int &num1,int &num2)
{
  if(length<2)
 return;
  int resultExclusiveOR=0;
  for(int i=0;i<length;i++)
 resultExclusiveOR^=data[i];
  unsigned int indexOf1=FindFirstBitIs1(resultExclusiveOR);
  num1=num2=0;
  for(int j=0;j<length;j++)
  {
    if(IsBit1(data[j],indexOf1))
num1^=data[j];
else
num2^=data[j];
  }
}

int main()
{
int a[8]={2,3,6,8,3,2,7,7};
int x,y;
FindNumsAppearOnce(a,8,x,y);
cout<<x<<" "<<y<<endl;
return 0;
}


    下面講解一個數組中出現三個只出現一次的數字,這個題目其實和上面類似。具體的題目與分析如下:

      題目:一個整型數組里有三個數字出現了一次,其他的數字都出現了兩次。請寫程序找出這3個只出現一次的數字。

分析:思路類似于上題,關鍵是找出第一個來,然后借助上題結論求另外兩個。

假設x y z為只出現一次的數,其他出現偶數次。lowbit為某個數從右往左掃描第一次出現1的位置,則x^y、 x^z、 y^z 這三個值的lowbit有一個規律,其中肯定兩個是一樣的,另外一個是不一樣的。令flips為上述三個值的異或,即flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)。因此,可以利用此條件獲得某個x(或者y,或者z),循環判斷的條件是a[i]^xors的lowbit==flips(其中xors為所有數的異或值)
解釋:a[i]^xors即可劃分為兩組,一組是lowbit與flips不同,一組是lowbit與flips相同。這樣就能找到某個x,y,z,找出后,將其與數組最后一個值交換,在利用上題思路,在前面n-1個數中找出剩余兩個。
    具體的代碼實現:

#include<iostream>
using namespace std;

int lowbit(int x)
{
  return x&~(x-1);
}

void Find2(int seq[],int n,int& a,int& b)
{
  int xors=0;
  for(int i=0;i<n;i++)
 xors^=seq[i];
  int diff=lowbit(xors);
  for(int j=0;j<n;j++)
  {
    if(diff & seq[j]) //與運算,表示數組中與異或結果位為1的位數相同
a^=seq[j];
else
b^=seq[j];
  }
}
//三個數兩兩的異或后lowbit有兩個相同,一個不同,可以分為兩組
void Find3(int seq[],int n,int &a,int &b,int &c)
{
  int i,xors=0;
  for(i=0;i<n;i++)
 xors^=seq[i];
  int flips=0;
  for(i=0;i<n;i++) //因為出現偶數次的seq[i]和xors的異或,異或結果不改變
 flips^=lowbit(xors^seq[i]); //表示的是:flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)
  //三個數兩兩異或后lowbit有兩個相同,一個不同,可以分為兩組
  //所以flips的值為:lowbit(a^b)或lowbit(a^c)或lowbit(b^c)
  //得到三個數中的一個
  a=0;
  for(i=0;i<n;i++)
  {
    if(lowbit(seq[i]^xors)==flips) //找到三個數兩兩異或后的lowbit與另外兩個lowbit不同的那個數。
a^=seq[i];
  }
  //找出后,與數組中最后一個值交換,利用Find2找出剩余的兩個。
  for(i=0;i<n;i++)
  {
    if(a==seq[i])
{
 int temp=seq[i];
 seq[i]=seq[n-1];
 seq[n-1]=temp;
}
  }
  //利用Find2,找出剩余的兩個
  Find2(seq,n-1,b,c);
}

int main(void)
{
int seq[]={2,3,3,2,4,6,4,10,9,8,8};
int a=0,b=0,c=0;
Find3(seq,11,a,b,c);
cout<<a<<endl;
cout<<b<<endl;
cout<<c<<endl;
return 0;
}
本文已影響
相關文章
大亨pk10计划苹果版