求數組中出現次數超過一半的元素

給定一個n個整型元素的數組a，其中有一個元素出現次數超過n / 2，求這個元素。據說是百度的一道題

分析

設置一個當前值和當前值的計數器，初始化當前值為數組首元素，計數器值為1，然后從第二個元素開始遍歷整個數組，對于每個被遍歷到的值a[i]

1 如果a[i]==currentValue，則計數器值加1

2 如果a[i] != currentValue， 則計數器值減1，如果計數器值小于0，則更新當前值為a[i]，并將計數器值重置為1

代碼

//找出數組中出現次數超過一半的元素
intFind(int*a,intn)
{
intcurValue=a[0];
intcount=1;

for(inti=1;iif(a[i]==curValue)
count++;
else
{
count--;
if(count0)
{
curValue=a[i];
count=1;
}
}
}

returncurValue;
}

另一個方法是先對數組排序，然后取中間元素即可，因為如果某個元素的個數超過一半，那么數組排序后該元素必定占據數組的中間位置。

求數組中元素的最短距離

給定一個含有n個元素的整型數組，找出數組中的兩個元素x和y使得abs(x - y)值最小

分析

先對數組排序，然后遍歷一次即可

代碼

intcompare(constvoid*a,constvoid*b)
{
return*(int*)a-*(int*)b;
}

//求數組中元素的最短距離
voidMinimumDistance(int*a,intn)
{
//Sort
qsort(a,n,sizeof(int),compare);

inti;//Indexofnumber1
intj;//Indexofnumber2

intminDistance=numeric_limits<int>::max();
for(intk=0;k1;++k)
{
if(a[k+1]-a[k]1]-a[k];
i=a[k];
j=a[k+1];
}
}

cout<"Minimumdistanceis:"<endl;
cout<"i="<"j="<endl;
}

求兩個有序數組的共同元素

給定兩個含有n個元素的有序（非降序）整型數組a和b，求出其共同元素，比如

a = 0, 1, 2, 3, 4

b = 1, 3, 5, 7, 9

輸出 1, 3

分析

充分利用數組有序的性質，用兩個指針i和j分別指向a和b，比較a[i]和b[j]，根據比較結果移動指針，則有如下三種情況

1. a[i] < b[j]，則i增加1，繼續比較

2. a[i] == b[j]，則i和j皆加1，繼續比較

3. a[i] < b[j]，則j加1，繼續比較

重復以上過程直到i或j到達數組末尾。

代碼

//找出兩個數組的共同元素
voidFindCommon(int*a,int*b,intn)
{
inti=0;
intj=0;

while(iif(a[i]elseif(a[i]==b[j])
{
cout<endl;
++i;
++j;
}
else//a[i]>b[j]
++j;
}
}

這到題還有其他的解法，比如對于a中任意一個元素，在b中對其進行Binary Search，因為a中有n個元素，而在b中進行Binary Search需要logn。所以找出全部相同元素的時間復雜度是O(nlogn)。

另外，上面的方法，只要b有序即可，a是否有序無所謂，因為我們只是在b中做Binary Search。

如果a也有序的話，那么再用上面的方法就有點慢了，因為如果a中某個元素在b中的位置是k的話，那么a中下一個元素在b中的位置一定位于k的右側，所以本次的搜索空間可以根據上次的搜索結果縮小，而不是仍然在整個b中搜索。也即如果a和b都有序的話，代碼可以做如下修改，記錄上次搜索時b中元素的位置，作為下一次搜索的起始點。

求三個數組的共同元素

給定三個含有n個元素的整型數組a,b和c，求他們最小的共同元素。

分析

如果三個數組都有序，那么可以設置三個指針指向三個數組的頭部，然后根據這三個指針所指的值進行比較來移動指針，直道找到共同元素。

代碼

//三個數組的共同元素-只找最小的
voidFindCommonElements(inta[],intb[],intc[],intx,inty,intz)
{
for(inti=0,j=0,k=0;iif(a[i]else//a[i]>=b[j]
{
if(b[j]else//b[j]>=c[k]
{
if(c[k]else//c[k]>=a[i]
{
cout<endl;
return;
}
}
}
}

cout<"Notfound!"<endl;
}

如果三個數組都無序，可以先對a, b進行排序，然后對c中任意一個元素都在b和c中做二分搜索。

代碼

//找出三個數組的共同元素
//O(NlogN)
intUniqueCommonItem(int*a,int*b,int*c,intn)
{
//sortarraya
qsort(a,n,sizeof(int),compare);//NlogN

//sortarrayb
qsort(b,n,sizeof(int),compare);//NlogN

//foreachelementinarrayc,doabinarysearchinaandb
//ThisisuptoacomplexityofN*2*logN
for(inti=0;iif(BinarySearch(a,n,c[i])&&BinarySearch(b,n,c[i]))
returnc[i];
}

return-1;//notfound
}

也可以對a進行排序，然后對于b和c中任意一個元素都在a中進行二分搜索，但是這樣做是有問題的，你看出來了么？感謝網友yy_5533指正。

代碼

//找出三個數組唯一的共同元素
//O(NlogN)
intUniqueCommonItem1(int*a,int*b,int*c,intn)
{
//sortarraya
qsort(a,n,sizeof(int),compare);//NlogN

//Spacefortime
bool*bb=newbool[n];
memset(bb,0,n);

bool*bc=newbool[n];
memset(bb,0,n);

//foreachelementinb,doaBSinaandmarkallthecommonelement
for(inti=0;i//NlogN
{
if(BinarySearch(a,n,b[i]))
bb[i]=true;
}

//foreachelementinc,doaBSonlyifb[i]istrue
for(inti=0;i//NlogN
{
if(b[i]&&BinarySearch(a,n,c[i]))
returnc[i];
}

return-1;//notfound
}

排序和二分搜索代碼如下

//Determinewhetheracontainsvaluek
boolBinarySearch(int*a,intn,intk)
{
intleft=0;
intright=n-1;
while(left<=?right)
????{
????????intmid=(left+right);

if(a[mid]1;
if(a[mid]==k)
returntrue;
else
right=mid-1;
}

returnfalse;
}

//Comparefunctionforqsort
intcompare(constvoid*a,constvoid*b)
{
return*(int*)a-*(int*)b;
}

小小總結一下，對于在數組中進行查找的問題，可以分如下兩種情況處理

1. 如果給定的數組有序，那么首先應該想到Binary Search，所需O(logn)

2. 如果給定的數組無序，那么首先應該想到對數組進行排序，很多排序算法都能在O(nlogn)時間內對數組進行排序，然后再使用二分搜索，總的時間復雜度仍是O(nlogn)。

如果能做到以上兩點，大多數關于數組的查找問題，都能迎刃而解。

找出數組中唯一的重復元素

給定含有1001個元素的數組，其中存放了1-1000之內的整數，只有一個整數是重復的，請找出這個數

分析

求出整個數組的和，再減去1-1000的和

代碼

略

找出出現奇數次的元素

給定一個含有n個元素的整型數組a，其中只有一個元素出現奇數次，找出這個元素。這道題實際上是一個變種，原題是找出數組中唯一一個出現一次的元素，下面的方法可以同時解決這兩道提。所以題目就用這個廣義的吧。

分析

因為對于任意一個數k，有k ^ k = 0，k ^ 0 = k，所以將a中所有元素進行異或，那么個數為偶數的元素異或后都變成了0，只留下了個數為奇數的那個元素。

代碼

intFindElementWithOddCount(int*a,intn)
{
intr=a[0];

for(inti=1;ireturnr;
}

求數組中滿足給定和的數對

給定兩個有序整型數組a和b，各有n個元素，求兩個數組中滿足給定和的數對，即對a中元素i和b中元素j，滿足i + j = d(d已知)

分析

兩個指針i和j分別指向數組的首尾，然后從兩端同時向中間遍歷。

代碼

//找出滿足給定和的數對
voidFixedSum(int*a,int*b,intn,intd)
{
for(inti=0,j=n-1;i=0)
{
if(a[i]+b[j]elseif(a[i]+b[j]==d)
{
cout<","<endl;
++i;
--j;
}
else//a[i]+b[j]>d
--j;
}
}

最大子段和

給定一個整型數組a，求出最大連續子段之和，如果和為負數，則按0計算，比如1， 2， -5， 6， 8則輸出6 + 8 = 14

分析

編程珠璣上的經典題目，不多說了。

代碼

//子數組的最大和
intSum(int*a,intn)
{
intcurSum=0;
intmaxSum=0;
for(inti=0;iif(curSum+a[i]0)
curSum=0;
else
{
curSum+=a[i];
maxSum=max(maxSum,curSum);
}
}
returnmaxSum;
}

最大子段積

給定一個整型數組a，求出最大連續子段的乘積，比如 1， 2， -8， 12， 7則輸出12 * 7 = 84

分析

與最大子段和類似，注意處理負數的情況

代碼

//子數組的最大乘積
intMaxProduct(int*a,intn)
{
intmaxProduct=1;//maxpositiveproductatcurrentposition
intminProduct=1;//minnegativeproductatcurrentposition
intr=1;//result,maxmultiplicationtotally

for(inti=0;iif(a[i]>0)
{
maxProduct*=a[i];
minProduct=min(minProduct*a[i],1);
}
elseif(a[i]==0)
{
maxProduct=1;
minProduct=1;
}
else//a[i]
{
inttemp=maxProduct;
maxProduct=max(minProduct*a[i],1);
minProduct=temp*a[i];
}

r=max(r,maxProduct);
}

returnr;
}

數組循環移位

將一個含有n個元素的數組向右循環移動k位，要求時間復雜度是O(n)，且只能使用兩個額外的變量，這是在微軟的編程之美上看到的一道題

分析

比如數組 1 2 3 4循環右移1位 將變成 4 1 2 3， 觀察可知1 2 3 的順序在移位前后沒有改變，只是和4的位置交換了一下，所以等同于1 2 3 4 先劃分為兩部分

1 2 3 | 4，然后將1 2 3逆序，再將4 逆序 得到 3 2 1 4，最后整體逆序 得到 4 1 2 3

代碼

//將buffer中start和end之間的元素逆序
voidReverse(intbuffer[],intstart,intend)
{
while(startinttemp=buffer[start];
buffer[start++]=buffer[end];
buffer[end--]=temp;
}
}

//將含有n個元素的數組buffer右移k位
voidShift(intbuffer[],intn,intk)
{
k%=n;

Reverse(buffer,0,n-k-1);
Reverse(buffer,n-k,n-1);
Reverse(buffer,0,n-1);
}

稍微擴展一下,如果允許分配額外的數組,那么定義一個新的數組,然后將移位后的元素直接存入即可,也可以使用隊列,將移動后得元素出對,再插入隊尾即可.

字符串逆序

給定一個含有n個元素的字符數組a，將其原地逆序。

分析

可能您覺得這不是關于數組的，而是關于字符串的。是的。但是別忘了題目要求的是原地逆序，也就是不允許額外分配空間，那么參數肯定是字符數組形式，因為字符串是不能被修改的（這里只C/C++中的字符串常量）。

所以，和數組有關了吧，只不過不是整型數組，而是字符數組。用兩個指針分別指向字符數組的首位，交換其對應的字符，然后兩個指針分別向數組中央移動，直到交叉。

代碼

//字符串逆序
voidReverse(char*a,intn)
{
intleft=0;
intright=n-1;

while(leftchartemp=a[left];
a[left++]=a[right];
a[right--]=temp;
}
}

組合問題

給定一個含有n個元素的整型數組a，從中任取m個元素，求所有組合。比如下面的例子

a = 1, 2, 3, 4, 5

m = 3

輸出

123,124,125,134,135,145

234,235,245
345

分析

典型的排列組合問題，首選回溯法，為了簡化問題，我們將a中n個元素值分別設置為1-n

代碼

//n選m的所有組合
intbuffer[100];

voidPrintArray(int*a,intn)
{
for(inti=0;icout<"";
cout<endl;
}

boolIsValid(intlastIndex,intvalue)
{
for(inti=0;iif(buffer[i]>=value)
returnfalse;
}
returntrue;
}

voidSelect(intt,intn,intm)
{
if(t==m)
PrintArray(buffer,m);
else
{
for(inti=1;i<=?n;?i++)
????????{
????????????buffer[t]?=?i;
????????????if(IsValid(t,i))
Select(t+1,n,m);
}
}
}

合并兩個數組

給定含有n個元素的兩個有序（非降序）整型數組a和b。合并兩個數組中的元素到整型數組c，要求去除重復元素并保持c有序（非降序）。例子如下

a = 1, 2, 4, 8

b = 1, 3, 5, 8

c = 1, 2, 3, 4, 5, 8

分析

利用合并排序的思想，兩個指針i,j和k分別指向數組a和b，然后比較兩個指針對應元素的大小，有以下三種情況

1. a[i] < b[j]，則c[k] = a[i]。

2. a[i] == b[j]，則c[k]等于a[i]或b[j]皆可。

3. a[i] > b[j]，則c[k] = b[j]。

重復以上過程，直到i或者j到達數組末尾，然后將剩下的元素直接copy到數組c中即可

代碼

//合并兩個有序數組
voidMerge(int*a,int*b,int*c,intn)
{
inti=0;
intj=0;
intk=0;

while(iif(a[i]//如果a的元素小，則插入a中元素到c
{
c[k++]=a[i];
++i;
}
elseif(a[i]==b[j])//如果a和b元素相等，則插入二者皆可，這里插入a
{
c[k++]=a[i];
++i;
++j;
}
else//a[i]>b[j]//如果b中元素小，則插入b中元素到c
{
c[k++]=b[j];
++j;
}
}

if(i==n)//若a遍歷完畢，處理b中剩下的元素
{
for(intm=j;melse//j==n,若b遍歷完畢，處理a中剩下的元素
{
for(intm=i;m

輸入0,3,0,2,1,0,0

輸出0,0,0,0,3,2,1

voidArrange(int*a,intn)
{
intk=n-1;
for(inti=n-1;i>=0;--i)
{
if(a[i]!=0)
{
if(a[k]==0)
{
a[k]=a[i];
a[i]=0;
}
--k;
}
}
}

boolSameSign(inta,intb)
{
if(a*b>0)
returntrue;
else
returnfalse;
}

//找出一個非遞減序整數序列中絕對值最小的數
intMinimumAbsoluteValue(int*a,intn)
{
//Onlyonenumberinarray
if(n==1)
{
returna[0];
}

//Allnumbersinarrayhavethesamesign
if(SameSign(a[0],a[n-1]))
{
returna[0]>=0?a[0]:a[n-1];
}

//Binarysearch
intl=0;
intr=n-1;

while(lif(l+1==r)
{
returnabs(a[l])abs(a[r])?a[l]:a[r];
}

intm=(l+r)/2;

if(SameSign(a[m],a[r]))
{
r=m-1;
continue;
}
if(SameSign(a[l],a[m]))
{
l=m+1;
continue;
}
}
}

//找出一個非遞減序整數序列中絕對值最小的數
intMinimumAbsoluteValue(int*a,intn)
{
//Onlyonenumberinarray
if(n==1)
{
returna[0];
}

//Allnumbersinarrayhavethesamesign
if(SameSign(a[0],a[n-1]))
{
returna[0]>=0?a[0]:a[n-1];
}

//Binarysearch
intl=0;
intr=n-1;

while(lif(l+1==r)
{
returnabs(a[l])abs(a[r])?a[l]:a[r];
}

intm=(l+r)/2;

if(SameSign(a[m],a[r]))
{
r=m;
continue;
}
else
{
l=m;
continue;
}
}
}