嵌入式C語言數(shù)組還能這樣玩？

數(shù)組求和

給定一個(gè)含有n個(gè)元素的整型數(shù)組a，求a中所有元素的和。可能您會(huì)覺得很簡單，是的，的確簡單，但是為什么還要說呢，原因有二，第一，這道題要求用遞歸法，只用一行代碼。第二，這是我人生中第一次面試時(shí)候遇到的題，意義特殊。

分析

簡單說一下，兩種情況

如果數(shù)組元素個(gè)數(shù)為0，那么和為0。

如果數(shù)組元素個(gè)數(shù)為n，那么先求出前n - 1個(gè)元素之和，再加上a[n - 1]即可

代碼

//數(shù)組求和
intsum(int*a,intn)
{
returnn==0?0:sum(a,n-1)+a[n-1];
}

求數(shù)組的最大值和最小值

給定一個(gè)含有n個(gè)元素的整型數(shù)組a，找出其中的最大值和最小值

分析

常規(guī)的做法是遍歷一次，分別求出最大值和最小值，但我這里要說的是分治法(Divide and couquer)，將數(shù)組分成左右兩部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后綜合起來求總體的最大值及最小值。

這是個(gè)遞歸過程，對于劃分后的左右兩部分，同樣重復(fù)這個(gè)過程，直到劃分區(qū)間內(nèi)只剩一個(gè)元素或者兩個(gè)元素。

代碼

//求數(shù)組的最大值和最小值，返回值在maxValue和minValue
voidMaxandMin(int*a,intl,intr,int&maxValue,int&minValue)
{
if(l==r)//l與r之間只有一個(gè)元素
{
maxValue=a[l];
minValue=a[l];
return;
}

if(l+1==r)//l與r之間只有兩個(gè)元素
{
if(a[l]>=a[r])
{
maxValue=a[l];
minValue=a[r];
}
else
{
maxValue=a[r];
minValue=a[l];
}
return;
}

intm=(l+r)/2;//求中點(diǎn)

intlmax;//左半部份最大值
intlmin;//左半部份最小值
MaxandMin(a,l,m,lmax,lmin);//遞歸計(jì)算左半部份

intrmax;//右半部份最大值
intrmin;//右半部份最小值
MaxandMin(a,m+1,r,rmax,rmin);//遞歸計(jì)算右半部份

maxValue=max(lmax,rmax);//總的最大值
minValue=min(lmin,rmin);//總的最小值
}

求數(shù)組的最大值和次大值

給定一個(gè)含有n個(gè)元素的整型數(shù)組，求其最大值和次大值

分析

思想和上一題類似，同樣是用分治法，先求出左邊的最大值leftmax和次大值leftsecond，再求出右邊的最大值rightmax和次大值rightsecond，然后合并，如何合并呢？分情況考慮

1 如果leftmax > rightmax，那么可以肯定leftmax是最大值，但次大值不一定是rightmax，但肯定不是rightsecond，只需將leftsecond與rightmax做一次比較即可。

2 如果rightmax > leftmax，那么可以肯定rightmax是最大值，但次大值不一定是leftmax，但肯定不是leftsecond，所以只需將leftmax與rightsecond做一次比較即可。

注意

這種方法無法處理最大元素有多個(gè)的情況，比如3,5,7,7將返回7，7而不是7,5。感謝網(wǎng)友 從無到有靠誰人 指出。

代碼

//找出數(shù)組的最大值和次大值，a是待查找的數(shù)組，left和right是查找區(qū)間，max和second存放結(jié)果
voidMaxandMin(inta[],intleft,intright,int&max,int&second)
{
if(left==right)
{
max=a[left];
second=INT_MIN;
}
elseif(left+1==right)
{
max=a[left]>a[right]?a[left]:a[right];
second=a[left]rightmax)
{
max=leftmax;
second=leftsecond>rightmax?leftsecond:rightmax;
}
else
{
max=rightmax;
second=leftmax

	

	求數(shù)組中出現(xiàn)次數(shù)超過一半的元素

	給定一個(gè)n個(gè)整型元素的數(shù)組a，其中有一個(gè)元素出現(xiàn)次數(shù)超過n / 2，求這個(gè)元素。據(jù)說是百度的一道題

	分析

	設(shè)置一個(gè)當(dāng)前值和當(dāng)前值的計(jì)數(shù)器，初始化當(dāng)前值為數(shù)組首元素，計(jì)數(shù)器值為1，然后從第二個(gè)元素開始遍歷整個(gè)數(shù)組，對于每個(gè)被遍歷到的值a[i]

	1 如果a[i]==currentValue，則計(jì)數(shù)器值加1

	2 如果a[i] != currentValue， 則計(jì)數(shù)器值減1，如果計(jì)數(shù)器值小于0，則更新當(dāng)前值為a[i]，并將計(jì)數(shù)器值重置為1

	代碼

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

for(inti=1;i

	

	另一個(gè)方法是先對數(shù)組排序，然后取中間元素即可，因?yàn)槿绻硞€(gè)元素的個(gè)數(shù)超過一半，那么數(shù)組排序后該元素必定占據(jù)數(shù)組的中間位置。

	求數(shù)組中元素的最短距離

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

	分析

	先對數(shù)組排序，然后遍歷一次即可

	代碼

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

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

inti;//Indexofnumber1
intj;//Indexofnumber2

intminDistance=numeric_limits::max();
for(intk=0;k

	

	求兩個(gè)有序數(shù)組的共同元素

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

	a = 0, 1, 2, 3, 4

	b = 1, 3, 5, 7, 9

	輸出 1, 3

	分析

	充分利用數(shù)組有序的性質(zhì)，用兩個(gè)指針i和j分別指向a和b，比較a[i]和b[j]，根據(jù)比較結(jié)果移動(dòng)指針，則有如下三種情況

	a[i] < b[j]，則i增加1，繼續(xù)比較

	a[i] == b[j]，則i和j皆加1，繼續(xù)比較

	a[i] < b[j]，則j加1，繼續(xù)比較

	重復(fù)以上過程直到i或j到達(dá)數(shù)組末尾。

	代碼

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

while(ib[j]
++j;
}
}


	

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

	另外，上面的方法，只要b有序即可，a是否有序無所謂，因?yàn)槲覀冎皇窃赽中做Binary Search。

	如果a也有序的話，那么再用上面的方法就有點(diǎn)慢了，因?yàn)槿绻鸻中某個(gè)元素在b中的位置是k的話，那么a中下一個(gè)元素在b中的位置一定位于k的右側(cè)，所以本次的搜索空間可以根據(jù)上次的搜索結(jié)果縮小，而不是仍然在整個(gè)b中搜索。也即如果a和b都有序的話，代碼可以做如下修改，記錄上次搜索時(shí)b中元素的位置，作為下一次搜索的起始點(diǎn)。

	求三個(gè)數(shù)組的共同元素

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

	分析

	如果三個(gè)數(shù)組都有序，那么可以設(shè)置三個(gè)指針指向三個(gè)數(shù)組的頭部，然后根據(jù)這三個(gè)指針?biāo)傅闹颠M(jìn)行比較來移動(dòng)指針，直道找到共同元素。

	代碼

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

	

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

	代碼

	
//找出三個(gè)數(shù)組的共同元素
//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;i

	

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

	代碼

	
//找出三個(gè)數(shù)組唯一的共同元素
//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

	

	排序和二分搜索代碼如下

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

????????if(a[mid]?

	

	小小總結(jié)一下，對于在數(shù)組中進(jìn)行查找的問題，可以分如下兩種情況處理

	如果給定的數(shù)組有序，那么首先應(yīng)該想到Binary Search，所需O(logn)

	如果給定的數(shù)組無序，那么首先應(yīng)該想到對數(shù)組進(jìn)行排序，很多排序算法都能在O(nlogn)時(shí)間內(nèi)對數(shù)組進(jìn)行排序，然后再使用二分搜索，總的時(shí)間復(fù)雜度仍是O(nlogn)。

	如果能做到以上兩點(diǎn)，大多數(shù)關(guān)于數(shù)組的查找問題，都能迎刃而解。

	找出數(shù)組中唯一的重復(fù)元素

	給定含有1001個(gè)元素的數(shù)組，其中存放了1-1000之內(nèi)的整數(shù)，只有一個(gè)整數(shù)是重復(fù)的，請找出這個(gè)數(shù)

	分析

	求出整個(gè)數(shù)組的和，再減去1-1000的和

	代碼

	略

	找出出現(xiàn)奇數(shù)次的元素

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

	分析

	因?yàn)閷τ谌我庖粋€(gè)數(shù)k，有k ^ k = 0，k ^ 0 = k，所以將a中所有元素進(jìn)行異或，那么個(gè)數(shù)為偶數(shù)的元素異或后都變成了0，只留下了個(gè)數(shù)為奇數(shù)的那個(gè)元素。

	代碼

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

for(inti=1;i

	

	求數(shù)組中滿足給定和的數(shù)對

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

	分析

	兩個(gè)指針i和j分別指向數(shù)組的首尾，然后從兩端同時(shí)向中間遍歷。

	代碼

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


	

	最大子段和

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

	分析

	編程珠璣上的經(jīng)典題目，不多說了。

	代碼

	
//子數(shù)組的最大和
intSum(int*a,intn)
{
intcurSum=0;
intmaxSum=0;
for(inti=0;i

	

	最大子段積

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

	分析

	與最大子段和類似，注意處理負(fù)數(shù)的情況

	代碼

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

for(inti=0;i0)
{
maxProduct*=a[i];
minProduct=min(minProduct*a[i],1);
}
elseif(a[i]==0)
{
maxProduct=1;
minProduct=1;
}
else//a[i]

	

	數(shù)組循環(huán)移位

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

	分析

	比如數(shù)組 1 2 3 4循環(huán)右移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(start

	

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

	字符串逆序

	給定一個(gè)含有n個(gè)元素的字符數(shù)組a，將其原地逆序。

	分析

	可能您覺得這不是關(guān)于數(shù)組的，而是關(guān)于字符串的。是的。但是別忘了題目要求的是原地逆序，也就是不允許額外分配空間，那么參數(shù)肯定是字符數(shù)組形式，因?yàn)樽址遣荒鼙恍薷牡模ㄟ@里只C/C++中的字符串常量）。

	所以，和數(shù)組有關(guān)了吧，只不過不是整型數(shù)組，而是字符數(shù)組。用兩個(gè)指針分別指向字符數(shù)組的首位，交換其對應(yīng)的字符，然后兩個(gè)指針分別向數(shù)組中央移動(dòng)，直到交叉。

	代碼

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

while(left

	

	組合問題

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

	a = 1, 2, 3, 4, 5

	m = 3

	輸出

	
123,124,125,134,135,145

234,235,245
345


	

	分析

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

	代碼

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

voidPrintArray(int*a,intn)
{
for(inti=0;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);
????????}
????}
}


	

	合并兩個(gè)數(shù)組

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

	a = 1, 2, 4, 8

	b = 1, 3, 5, 8

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

	分析

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

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

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

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

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

	代碼

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

while(ib[j]//如果b中元素小，則插入b中元素到c
{
c[k++]=b[j];
++j;
}
}

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

	

	重排問題

	給定含有n個(gè)元素的整型數(shù)組a，其中包括0元素和非0元素，對數(shù)組進(jìn)行排序，要求：

	排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相對位置不變

	不能使用額外存儲(chǔ)空間

	例子如下

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

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


	

	分析

	此排序非傳統(tǒng)意義上的排序，因?yàn)樗笈判蚯昂蠓?元素的相對位置不變，或許叫做整理會(huì)更恰當(dāng)一些。我們可以從后向前遍歷整個(gè)數(shù)組，遇到某個(gè)位置i上的元素是非0元素時(shí)，如果a[k]為0，則將a[i]賦值給a[k]，a[k]賦值為0。實(shí)際上i是非0元素的下標(biāo)，而k是0元素的下標(biāo)

	代碼

	
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;
}
}
}


	

	找出絕對值最小的元素

	給定一個(gè)有序整數(shù)序列（非遞減序），可能包含負(fù)數(shù)，找出其中絕對值最小的元素，比如給定序列 -5, -3, -1, 2, 8 則返回1。

	分析

	由于給定序列是有序的，而這又是搜索問題，所以首先想到二分搜索法，只不過這個(gè)二分法比普通的二分法稍微麻煩點(diǎn)，可以分為下面幾種情況

	如果給定的序列中所有的數(shù)都是正數(shù)，那么數(shù)組的第一個(gè)元素即是結(jié)果。

	如果給定的序列中所有的數(shù)都是負(fù)數(shù)，那么數(shù)組的最后一個(gè)元素即是結(jié)果。

	如果給定的序列中既有正數(shù)又有負(fù)數(shù)，那么絕對值得最小值一定出現(xiàn)在正數(shù)和負(fù)數(shù)的連接處。

	為什么？

	因?yàn)閷τ谪?fù)數(shù)序列來說，右側(cè)的數(shù)字比左側(cè)的數(shù)字絕對值小，如上面的-5, -3, -1, 而對于整整數(shù)來說，左邊的數(shù)字絕對值小，比如上面的2, 8，將這個(gè)思想用于二分搜索，可先判斷中間元素和兩側(cè)元素的符號，然后根據(jù)符號決定搜索區(qū)間，逐步縮小搜索區(qū)間，直到只剩下兩個(gè)元素。

	代碼

	單獨(dú)設(shè)置一個(gè)函數(shù)用來判斷兩個(gè)整數(shù)的符號是否相同。

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


	

	主函數(shù)代碼。

	
//找出一個(gè)非遞減序整數(shù)序列中絕對值最小的數(shù)
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(l

	

	這段代碼是有問題的，感謝網(wǎng)友lingyunfish的指正，你看出來了么？修改后的代碼如下：

	
//找出一個(gè)非遞減序整數(shù)序列中絕對值最小的數(shù)
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(l

	

	來源：https://www.cnblogs.com/graphics/archive/2010/08/24/1761620.html

	





	審核編輯：劉清