Java程序員面試分類(lèi)模擬16

Java程序員面試分類(lèi)模擬16論述題1.

如何找出數(shù)組中重復(fù)元素最多的數(shù)正確答案：?jiǎn)栴}描述：對(duì)于數(shù)組{1，1，2，2，4，4，4，4，5，5，6，6，6}，元素1出現(xiàn)的次數(shù)為2次，元素2出現(xiàn)的次數(shù)（江南博哥）為2次，元素4出現(xiàn)的次數(shù)為4次，元素5出現(xiàn)的次數(shù)為2次，元素6出現(xiàn)的次數(shù)為3次，找出數(shù)組中出現(xiàn)重復(fù)次數(shù)最多的數(shù)。

上述問(wèn)題中，程序的輸出應(yīng)該為元素4。

可以采取如下兩種方法來(lái)計(jì)算數(shù)組中重復(fù)次數(shù)最多的數(shù)。

方法一：空間換時(shí)間?？梢远x一個(gè)數(shù)組intcount[MAX]，并將其數(shù)組元素都初始化為0，然后執(zhí)行for(inti=0;i＜100;i++)count[A[i]]++操作，在count數(shù)組中找最大的數(shù)，即為重復(fù)次數(shù)最多的數(shù)。這是一種典型的空間換時(shí)間的算法。一般情況下，除非內(nèi)存空間足夠大，一般不采用這種方法。

方法二：使用Map映射表。通過(guò)引入Map映射表(Map提供一對(duì)一的數(shù)據(jù)處理能力，其中第一個(gè)為關(guān)鍵字，每個(gè)關(guān)鍵字只能在Map中出現(xiàn)一次，第二個(gè)稱為該關(guān)鍵字的值)來(lái)記錄每一個(gè)元素出現(xiàn)的次數(shù)，然后判斷次數(shù)大小，進(jìn)而找出重復(fù)次數(shù)最多的元素。示例如下：

importjava.util.*;

publicclassTest{

publicstaticintfindMostFrequentInArray(int[]a){

intresult=0;

intsize=a.length;

if(size==0)

returnInteger.MAX_VALUE;

//記錄每個(gè)元素出現(xiàn)的次數(shù)

Map＜Integer,Integer＞m=newHashMap＜Integer,Integer＞();

for(inti=0;i＜size;i++){

if(m.containsKey(a[i])){

m.put(a[i],m.get(a[i])+1);

}

else{

m.put(a[i],1);

}

}

//找出出現(xiàn)次數(shù)最多的元素

intmost=0;

Iteratoriter=m.entrySet().iterator();

while(iter.hasNext()){

Map.Entryentry==(Map.Entry)iter.next();

intkey=(Integer)entry.getKey();

intval=(Integer)entry.getValue();

if(val＞most){

result=key;

most=val;

}

}

returnresult;

}

publicstaticvoidmain(Stnng[]args){

intarray[]={1,5,4,3,4,4,5,4,5,5,6,6,6,6,6};

intmaxFrequenceNum=findMostFrequentInArray(array);

System.out.println(maxFrequenceNum);

}

}

程序運(yùn)行結(jié)果為：

6

2.

如何求數(shù)組中兩兩相加等于20的組合種數(shù)正確答案：?jiǎn)栴}描述：給定一個(gè)數(shù)組{1，7，17，2，6，3，14}，這個(gè)數(shù)組中滿足條件的有兩對(duì)組合——17+3=20和6+14=20。

方法一：“蠻力”法

最容易想到的方法就是采用兩重循環(huán)遍歷數(shù)組來(lái)判斷兩個(gè)數(shù)的和是否為20。實(shí)現(xiàn)代碼如下：

publicclassTest{

publicstaticvoidfindSum(int[]a,intsum){

intlen=a.length;

for(inti=0;i＜len;i++)

for(intj=i;j＜len;j++){

if(a[i]+a[j]==sum)

System.out.println(a[i]+","+a[j]);

}

}

publicstaticvoidmain(String[]args){

intarray[]={1,7,17,2,6,3,14};

findSum(array,20);

}

}

程序運(yùn)行結(jié)果為：

17,3

6,14

由于采用了雙重循環(huán)，因此這個(gè)算法的時(shí)間復(fù)雜度為O(n^2)。

方法二：排序法

先對(duì)數(shù)組元素進(jìn)行排序，可以選用堆排序或快速排序，此時(shí)算法的時(shí)間復(fù)雜度為O(nlogn)，然后對(duì)排序后的數(shù)組分別從前到后和從后到前遍歷，假設(shè)從前往后遍歷的下標(biāo)為begin，從后往前遍歷的下標(biāo)為end，那么當(dāng)滿足arr[begin]+arr[end]＜20時(shí)，如果存在兩個(gè)數(shù)的和為20，那么這兩個(gè)數(shù)一定在[begin+1，end]之間；當(dāng)滿足arr[begin]+arr[end]＞20時(shí)，如果存在兩個(gè)數(shù)的和為20，那么這兩個(gè)數(shù)一定在[begin，end+1]之間。這個(gè)過(guò)程的時(shí)間復(fù)雜度為O(n)，因此整個(gè)算法的時(shí)間復(fù)雜度為O(nlogn)。實(shí)現(xiàn)代碼如下：

importjava.util.Arrays;

publicclassTest{

publicstaticvoidfindSum(int[]a,intsum){

Arrays.sort(a);

intbegin=0;

intend=a.length-1;

while(begin＜end){

if(a[begin]+a[end]＜sum)

begin++;

elseif(a[begin]+a[end]＞sum)

end--;

else{

System.out.println(a[begin]+","+a[end]);

begin++;

end--;

}

}

}

publicstaticvoidmain(String[]args){

intarray[]={1,7,17,2,6,3,14};

findSum(array,20);

}

}

程序運(yùn)行結(jié)果為：

3,17

6,14

這個(gè)算法的時(shí)間復(fù)雜度主要由排序算法的時(shí)間復(fù)雜度來(lái)決定。因此，選擇時(shí)間復(fù)雜度較低的排序算法能顯著提高該算法的效率。

3.

如何把一個(gè)數(shù)組循環(huán)右移k位正確答案：假設(shè)要把數(shù)組序列12345678右移2位變?yōu)?8123456，比較移位前后數(shù)組序列的形式，不難看出，其中有兩段序列的順序是不變的，即78和123456，可以把這兩段看作兩個(gè)整體，右移k位就是把數(shù)組的兩部分交換一下。鑒于此，可以設(shè)計(jì)這樣一種算法，步驟如下(以數(shù)組序列12345678為例)：

1)逆序數(shù)組子序列123456，數(shù)組序列的形式變?yōu)?5432178。

2)逆序數(shù)組子序列78，數(shù)組序列的形式變?yōu)?5432187。

3)全部逆序，數(shù)組序列的形式變?yōu)?8123456。

程序代碼如下：

publicclassTest{

publicstaticvoidreverse(inta[],intb,inte){

for(;b＜e;b++,e--){

inttemp=a[e];

a[e]=a[b];

a[b]=temp;

}

}

publicstaticvoidshift_k(inta[],intk){

intn=a.length;

k=k%n;//為了防止k比n大，右移k位跟右移k%n位的結(jié)果是一樣的

reverse(a,n-k,n-1);

reverse(a,0,n-k-1);

reverse(a,0,n-1);

}

publicstaricvoidmain(String[]args){

intarray[]={1,2,3,4,5,6,7,8};

shift_k(array,2);

for(inti=0;i＜array.length;i++){

System.out.print(array[i]+"");

}

}

}

程序運(yùn)行結(jié)果如下：

78123456

從上例中可以看出，該算法只進(jìn)行了3次逆序操作，因此時(shí)間復(fù)雜度為O(n)。

4.

如何找出數(shù)組中第k個(gè)最小的數(shù)正確答案：?jiǎn)栴}描述：給定一個(gè)無(wú)序的數(shù)組，從一個(gè)數(shù)組中找出第k個(gè)最小的數(shù)，例如，對(duì)于給定數(shù)組序列{1，5，2，6，8，0，6}，其中第4小的數(shù)為5。

方法一：排序法

最容易想到的方法就是對(duì)數(shù)組進(jìn)行排序，排序后的數(shù)組中第k-1個(gè)位置上的數(shù)字即為數(shù)組的第k個(gè)最小的數(shù)(原因是數(shù)組下標(biāo)從0開(kāi)始計(jì)數(shù))，這種方法最好的時(shí)間復(fù)雜度為O(nlogn)。

方法二：“剪枝”法

采用快速排序的思想來(lái)實(shí)現(xiàn)。主要思路如下：選一個(gè)數(shù)tmp=a[n-1]作為樞紐，把比它小的數(shù)都放在它的左邊，比它大的數(shù)都放在它的右邊，然后判斷tmp的位置，如果它的位置為k-1，那么它就是第k個(gè)最小的數(shù)；如果它的位置小于k-1，那么說(shuō)明第k個(gè)小的元素一定在數(shù)組的右半部分，采用遞歸的方法在數(shù)組的右半部分繼續(xù)查找；否則第k個(gè)小的元素在數(shù)組的左半部分，采用遞歸的方法在左半部分?jǐn)?shù)組中繼續(xù)查找。示例如下：

publicclassTest{

publicstaticintquikSort(intarray[],intlow,inthigh,intk){

inti,j;

inttmp;

if(low＞high)

returnInteger.MIN_VALUE;

i=low+1;

j=high;

tmp=array[i];

while(i＜j){

while(i＜j&&array[j]＞=tmp)

j--;

if(i＜j)

array[i++]=array[j];

while(i＜j&&array[i]＜tmp)

i++;

if(i＜j)

array[j--]=array[i];

}

array[i]=tmp;

if(i+1==k)

returntmp;

elseif(i+1＞k)

returnquikSort(array,low,i-1,k);

else

returnquikSort(array,i+1,high,k);

}

publicstaticintgetKMin(intarray[],intk){

if(array==null)

returnInteger.MIN_VALUE;

if(array.length＜k)

returnInteger.MIN_VALUE;

returnquikSort(array,0,array.length-1,k);

}

publicstaticvoidmain(String[]args){

inta[]={1,5,2,6,8,0,6};

intkMin=getKMin(a,4);

System.out.println(kMin);

}

}

程序運(yùn)行結(jié)果為：

5

表面上看起來(lái)這種方法還是在對(duì)數(shù)組進(jìn)行排序，但是它比排序法的效率高，主要原因是當(dāng)在數(shù)組右半部分遞歸查找時(shí)，完全不需要關(guān)注左半部分?jǐn)?shù)組的順序，因此省略了對(duì)左半部分?jǐn)?shù)組的排序。因此，這種方法可以被看作一種“剪枝”方法，不斷縮小問(wèn)題的規(guī)模，直到找到第k個(gè)小的元素。

5.

如何找出數(shù)組中只出現(xiàn)一次的數(shù)字正確答案：?jiǎn)栴}描述：一個(gè)整型數(shù)組里除了一個(gè)數(shù)字之外，其他數(shù)字都出現(xiàn)了兩次。找出這個(gè)只出現(xiàn)1次的數(shù)字。要求時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。

如果本題對(duì)時(shí)間復(fù)雜度沒(méi)有要求，最容易想到的方法就是先對(duì)這個(gè)整型數(shù)組排序，然后從第一個(gè)數(shù)字開(kāi)始遍歷，比較相鄰的兩個(gè)數(shù)，從而找出這個(gè)只出現(xiàn)1次的數(shù)字，這種方法的時(shí)間復(fù)雜度最快為O(nlogn)。

由于時(shí)間復(fù)雜度與空間復(fù)雜度的限制，該方法不可取，因此需要一種更高效的方式。題目強(qiáng)調(diào)只有一個(gè)數(shù)字出現(xiàn)1次，其他數(shù)字出現(xiàn)了兩次，首先想到的是異或運(yùn)算，根據(jù)異或運(yùn)算的定義可知，任何一個(gè)數(shù)字異或它自己都等于0，所以，如果從頭到尾依次異或數(shù)組中的每一個(gè)數(shù)字，那些出現(xiàn)兩次的數(shù)字全部在異或中會(huì)被抵消掉，最終的結(jié)果剛好是這個(gè)只出現(xiàn)1次的數(shù)字。示例如下：

publicclassTest{

publicstaticintfindNotDouble(inta[]){

intn=a.length;

intresuh=a[0];

inti;

for(i=1;i＜n;++j)

result^=a[i];

returnresult;

}

publicstaticvoidmain(String[]args){

intarray[]={1,2,3,2,4,3,5,4,1};

intnum=findNotDouble(array);

System.out.println(num);

}

}

程序運(yùn)行結(jié)果為：

5

引申：如果題目改為數(shù)組A中，一個(gè)整型數(shù)組里除了一個(gè)數(shù)字之外，其他數(shù)字都出現(xiàn)了3次，那么如何找出這個(gè)數(shù)?

上述異或運(yùn)算的方法只適用于其他數(shù)字出現(xiàn)的次數(shù)為偶數(shù)的情況，如果其他數(shù)字出現(xiàn)的次數(shù)為奇數(shù)，上述介紹的方法則不再適用。如果數(shù)組中的所有數(shù)都出現(xiàn)n次，那么這個(gè)數(shù)組中的所有數(shù)對(duì)應(yīng)的二進(jìn)制數(shù)中，各個(gè)位上的1出現(xiàn)的個(gè)數(shù)均可以被n整除。以n=3為例，假如數(shù)組中有如下元素：{1，1，1，2，2，2}，它們對(duì)應(yīng)的二進(jìn)制表示為01，01，01，10，10，10。顯然，這個(gè)數(shù)組中的所有數(shù)字對(duì)應(yīng)的二進(jìn)制數(shù)中第0位有3個(gè)1，第1位有3個(gè)1。對(duì)于本題而言，假設(shè)出現(xiàn)一次的這個(gè)數(shù)為a，那么去掉a后其他所有數(shù)字對(duì)應(yīng)的二進(jìn)制數(shù)的每個(gè)位置出現(xiàn)1的個(gè)數(shù)為3的倍數(shù)。因此可以對(duì)數(shù)組中的所有數(shù)字對(duì)應(yīng)的二進(jìn)制數(shù)中各個(gè)位置上1的個(gè)數(shù)對(duì)3取余數(shù)，就可以得到出現(xiàn)1次的這個(gè)數(shù)的二進(jìn)制表示，從而可以找出這個(gè)數(shù)。示例如下：

publicclassTest{

publicstaticintfindOnee(inta[],intappearTimes){

intn=a.length;

int[]bitCount=newint[32];

//計(jì)算數(shù)組中所有數(shù)組對(duì)應(yīng)的二進(jìn)制數(shù)各個(gè)位置上出現(xiàn)1的次數(shù)

for(inti=0;i＜n;i++)

for(intj=0;j＜32;j++)

bitCount[j]+=((a[i]>>j)&1);

//若某位上的結(jié)果不能被整除，則肯定目標(biāo)數(shù)字在這一位上

intappearOne=0;

for(inti=0;i＜32;i++)

if(bitCount[i]%appearTimes!=0)

appearOne+=(1<<i);

returnappearOne;

}

publicstaticvoidnlain(String[]args){

intarray[]={1,2,1,2,4,2,4,4,1,3};

intnum=findOnce(array,3);

System.out.println(num);

}

}

程序運(yùn)行結(jié)果為：

3

此外，這種方法不僅適用于求解其他數(shù)字出現(xiàn)個(gè)數(shù)為奇數(shù)的情況，也適用于求解出現(xiàn)次數(shù)為偶數(shù)的情況，具有更好的通用性。

6.

如何找出數(shù)組中唯一的重復(fù)元素正確答案：?jiǎn)栴}描述：數(shù)組a[N]，1～N-1這N-1個(gè)數(shù)存放在a[N]中，其中某個(gè)數(shù)重復(fù)1次。寫(xiě)一個(gè)函數(shù)，找出被重復(fù)的數(shù)字。要求每個(gè)數(shù)組元素只能訪問(wèn)1次，并且不用輔助存儲(chǔ)空間。

由于題目要求每個(gè)數(shù)組元素只能訪問(wèn)1次，且不用輔助存儲(chǔ)空間，因此可以從原理上入手，采用數(shù)學(xué)求和法，因?yàn)橹挥幸粋€(gè)數(shù)字重復(fù)1次，而又是連續(xù)的，根據(jù)累加和原理，對(duì)數(shù)組的所有項(xiàng)求和，然后減去1～N-1的和，即為所求的重復(fù)數(shù)。示例如下：

publicclassTest{

publicstaticintxor_findDup(int[]a){

intn=a.length;

inttmp1=0;

inttmp2=0;

for(inti=0;i＜n-1;++i){

tmp1+=(i+1);

tmp2+=a[i];

}

tmp2+=a[n-1];

intresult=tmp2-tmp1;

returnresult;

}

publicstaticvoidmain(String[]args){

inta[]={1,2,1,3,4};

intmissingNum=xor_findDup(a);

System.out.println(missingNum);

}

}

程序運(yùn)行結(jié)果為：

1

如果題目沒(méi)有要求每個(gè)數(shù)組元素只能訪問(wèn)1次，且不允許使用輔助存儲(chǔ)空間，還可以用異或法和位圖法來(lái)求解。

(1)異或法

根據(jù)異或法的計(jì)算方式，每?jī)蓚€(gè)相異的數(shù)執(zhí)行異或運(yùn)算之后，結(jié)果為1；每?jī)蓚€(gè)相同的數(shù)執(zhí)行異或運(yùn)算之后，結(jié)果為0，所以，數(shù)組a[N]中的N個(gè)數(shù)異或結(jié)果與1～N-1異或的結(jié)果再做異或運(yùn)算，得到的值即為所求。

設(shè)重復(fù)數(shù)為A，其余N-2個(gè)數(shù)異或結(jié)果為B，N個(gè)數(shù)異或結(jié)果為A^A^B，1～N-1異或結(jié)果為A^B，由于異或滿足交換律和結(jié)合律，且X^X=0，0^X=X，則有(A^B)^(A^A^B)=A^B^B=A。示例如下：

publicclassTest{

publicstaticintxor_findDup(int[]a){

intn=a.length;

inti;

intresult=0;

for(i=0;i＜n;i++){

result^=a[i];

}

for(i=1;i＜n;i++){

result^=i;

}

returnresult;

}

publicstaticvoidmain(String[]args){

inta[]={1,2,1,3,4};intmissingNum=xor_findDup(a);

System.out.println(missingNum);

}

}

程序運(yùn)行結(jié)果為：

1

(2)空間換時(shí)間法

申請(qǐng)長(zhǎng)度為N-1的整型數(shù)組flag并初始化為0，然后從頭開(kāi)始遍歷數(shù)組a，取每個(gè)數(shù)組元素a[i]的值，將其對(duì)應(yīng)的數(shù)組flag中的元素賦值為1，如果已經(jīng)置過(guò)1，那么該數(shù)就是重復(fù)的數(shù)。示例如下：

publicclassTest{

publicstaticintfindInteger(int[]a){

intn=a.length;

boolean[]arrayflag=newboolean[n];

inti=1;

intresult=Integer.MAX_VALUE;

while(i＜n){

arrayflag[i]=false;

i++;

}

for(i=0;i＜n;i++){

if(arrayflag[a[i]]==false)

arrayflag[a[i]]=true;

else{

result=a[i];

}

}

returnresult;

}

publicstaricvoidmain(String[]args){

inta[]={1,2,1,3,4};

intmissingNum=findInteger(a);

System.out.println(missingNum);

}

}

程序運(yùn)行結(jié)果為：

1

這種方法的空間復(fù)雜度比較大，需要申請(qǐng)長(zhǎng)度為N的整數(shù)數(shù)組。當(dāng)然也可以通過(guò)使用位圖的方法來(lái)降低空間復(fù)雜度，即不是用一個(gè)整型數(shù)字來(lái)表示元素是否出現(xiàn)過(guò)(0表示未出現(xiàn)，1表示出現(xiàn)過(guò))，而是使用1bit來(lái)表示，因此需要申請(qǐng)數(shù)組的長(zhǎng)度為N/32取上整。

此題可以進(jìn)行一個(gè)變形：取值為[1，n-1]含n個(gè)元素的整數(shù)數(shù)組，至少存在一個(gè)重復(fù)數(shù)，即可能存在多個(gè)重復(fù)數(shù)，O(n)時(shí)間內(nèi)找出其中任意一個(gè)重復(fù)數(shù)，例如，array[]={1，2，2，4，5，4}，則2和4均是重復(fù)元素。

方案一：位圖法。使用大小為n的位圖，記錄每個(gè)元素是否已經(jīng)出現(xiàn)過(guò)，一旦遇到一個(gè)已經(jīng)出現(xiàn)過(guò)的元素，則直接將之輸出。該方法的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度為O(n)。

方案二：數(shù)組排序法。先對(duì)數(shù)組進(jìn)行計(jì)數(shù)排序，然后順序掃描整個(gè)數(shù)組，一旦遇到一個(gè)已出現(xiàn)的元素，則直接將之輸出。該方法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。

以上提出的兩種方案都需要額外的存儲(chǔ)空間，能否不使用額外存儲(chǔ)空間呢?答案是可以。于是想到了方案三：取反法。取反：去的基本思路如下：如果遍歷到數(shù)組中的元素為i，那么把a(bǔ)[i]的值取反，如果i在數(shù)組中出現(xiàn)兩次，那么a[i]會(huì)經(jīng)過(guò)兩次取反操作，a[i]的值跟原始的值相等，且為正數(shù)；如果i出現(xiàn)了1次，那么a[i]的值為原始值的相反數(shù)，且為負(fù)數(shù)，可以根據(jù)這個(gè)原理來(lái)實(shí)現(xiàn)。實(shí)現(xiàn)方法如下：將數(shù)組元素值作為索引，對(duì)于元素arry[i]，如果array[array[i]]大于0，那么設(shè)置array[array[i]]=-array[array[i]]；如果array[array[i]]小于0，那么設(shè)置array-[array[i]]=-array[-array[i]]，最后從數(shù)組第二個(gè)元素開(kāi)始遍歷數(shù)組，如果array[i]＞0，那么這個(gè)數(shù)就是重復(fù)的。由于在進(jìn)行遍歷后對(duì)數(shù)組中的數(shù)據(jù)進(jìn)行了修改，因此需要對(duì)數(shù)據(jù)進(jìn)行還原(對(duì)數(shù)組中的負(fù)數(shù)取反)。示例如下：

publicclassTest{

publicstaticintxor_findDup(int[]a){

intn=a.length;

intresult=Integer.MAX_VALUE;

for(inti=0;i＜n;i++){

if(a[i]＞0){

a[a[i]]=-a[a[i]];

}else{

a[-a[i]]=-a[-a[i]];

}

}

for(inti=1;i＜n;i++){

if(a[i]＞0)

result=i;

else

a[i]=-a[i];

}

returnresult;

}

publicstaticvoidmain(String[]args){

inta[]={4,2,1,3,4};

intmissingNum=xor_findDup(a);

System.out.println(missingNum);

}

}

方法四是一種非?！霸幃悺钡乃惴?，就是采用類(lèi)似于單鏈表是否存在環(huán)的問(wèn)題。“判斷單鏈表是否存在環(huán)”是一個(gè)非常經(jīng)典的問(wèn)題，同時(shí)單鏈表可以采用數(shù)組實(shí)現(xiàn)，此時(shí)每個(gè)元素值作為next指針指向下一個(gè)元素。本題可以轉(zhuǎn)化為“已知一個(gè)單鏈表中存在環(huán)，找出環(huán)的入口點(diǎn)”這種想法。具體思路如下：將array[i]看作第i個(gè)元素的索引，即array[i]→array[array[i]]→array[array[array[i]]]→array[array[array[array[i]]]]→…，最終形成一個(gè)單鏈表，由于數(shù)組a中存在重復(fù)元素，因此一定存在一個(gè)環(huán)，且環(huán)的入口元素即為重復(fù)元素。

該題的關(guān)鍵在于，數(shù)組array的長(zhǎng)度是n，而元素的范圍是[1，n-1]，所以array[0]不會(huì)指向自己，進(jìn)而不會(huì)陷入錯(cuò)誤的自循環(huán)。如果元素的范圍中包含0，那么該題不可直接采用該方法。示例如下：

publicclassTest1{

publicstaticintfindInteger(inta[]){

intx,y;

x=y=0;

do{

x=a[a[x]];

//x一次走兩步

y=a[y];

//y一次走一步

}while(x!=y);

//找到環(huán)中的一個(gè)點(diǎn)

x=0;

do{

x=a[x];

y=a[y];

}while(x!=y);

//找到入口點(diǎn)

returnx;

}

publicstaticvoidmain(String[]args){

inta[]={1,2,1,3,4};

intmissingNum=findInteger(a);

System.out.println(missingNum);

}

}

程序運(yùn)行結(jié)果為：

1

7.

如何用遞歸方法求一個(gè)整數(shù)數(shù)組的最大元素正確答案：對(duì)于本題而言，最容易實(shí)現(xiàn)的方法為對(duì)數(shù)組進(jìn)行遍歷，定義一個(gè)變量max為數(shù)組的第一個(gè)元素，然后從第二個(gè)元素開(kāi)始遍歷，在遍歷過(guò)程中，每個(gè)元素都與max的值進(jìn)行比較，若該元素的值比max的值大，則把該元素的值賦給max。當(dāng)遍歷完數(shù)組后，最大值也就求出來(lái)了。而使用遞歸方法求解的主要思路為：遞歸的求解“數(shù)組第一個(gè)元素”與“數(shù)組中其他元素組成的子數(shù)組的最大值”的最大值。示例如下：

publicclassTest{

privateintmax(inta,intb){

returna＞b?a:b;p

}

publicintmaxnum(inta[],intbegin){

intlength=a.length-begin;

it(length==1)

returna[begin];

else{

returnmax(a[begin],maxnum(a,begin+1));

}

}

publicstaticvoidmain(String[]args){

Testt=newTest();

int[]num={0,16,2,3,4,5,10,7,8,9};

System.out.println(t.maxnum(num,0));

}

}

程序運(yùn)行結(jié)果為：

16

8.

如何求數(shù)對(duì)之差的最大值正確答案：?jiǎn)栴}描述：數(shù)組中的一個(gè)數(shù)字減去它右邊子數(shù)組中的一個(gè)數(shù)字可以得到一個(gè)差值，求所有可能的差值中的最大值，例如，數(shù)組{1，4，17，3，2，9}中，最大的差值為17-2=15。

方法一：“蠻力”法?！靶U力”法也是最容易想到的方法，其原理如下：首先，遍歷數(shù)組，找到所有可能的差值；其次，從所有差值中找出最大值。具體實(shí)現(xiàn)方法為：針對(duì)數(shù)組a中的每個(gè)元素a[i](0＜i＜n-1)，求所有a[i]-a[j](i＜j＜n)的值中的最大值。示例如下：

publicclassTest{

publicstaticintgetMax(int[]a){

if(a==null)

returnInteger.MIN_VALUE;

intlen=a.length;

if(len＜=1)

returnInteger.MIN_VALUE;

intmax=Integer.MIN_VALUE;

for(inti=0;i＜len-1;i++){

tbr(intj=i+1;j＜len;j++)

if(a[i]-a[j]＞max)

max=a[i]-a[j];

}

returnmax;

}

publicstaticvoidmain(String[]args){

int[]a={1,4,17,3,2,9};

System.out.println(getMax(a));

}

}

程序運(yùn)行結(jié)果為：

15

采用這種方法雖然也能求出最大值，但是它的時(shí)間復(fù)雜度為O(n)。

方法二：二分法。通過(guò)二分法可以減少計(jì)算的次數(shù)。思路如下：把數(shù)組分為兩個(gè)子數(shù)組，那么最大的差值只能有3種可能：①最大的差值對(duì)應(yīng)的被減數(shù)和減數(shù)都在左子數(shù)組中，假設(shè)最大差值為leftMax；②被減數(shù)和減數(shù)都在右子數(shù)組中，假設(shè)最大差值為rightMax；③被減數(shù)是左子數(shù)組的最大值，減數(shù)是右子數(shù)組中的最小值，假設(shè)差值為mixMax。那么就可以得到這個(gè)數(shù)組的最大差值為這3個(gè)差值的最大值，即max(leftMax，rightNax，mixMax)。實(shí)現(xiàn)代碼如下：

importjavautil.concurrent.atomic.AtomicInteger;

publicclassTest{

publicstaticintgetMax(inta[]){

if(a==null)

returnInteger.MIN_VALUE;

intlen=a.length;

if(len＜=1)

returnInteger.MIN_VALUE;

AtomicIntegermax=newAtomicInteger(0);

AtomicIntegermin=newAtomicInteger(0);

returngetMaxDiff(a,0,len-1,max,min);

}

publicstaticintgetMaxDiff(inta[],intbegin,intend,AtomicIntegermax,AtomicIntegermin){

if(begin==end){

max.set(a[begin]);

min.set(a[begin]);

returnInteger.MIN_VALUE;

}

intmiddle=begin+(end-begin)/2;

//數(shù)組前半部分的最小值與最大值

AtomicIntegerlMax=newAtomicInteger(0);

AtomicIntegerlMin=newAtomicInteger(0);

//數(shù)組前半部分的最：趕差值(第一種情況)

intleflMax=getMaxDiff(a,begin,middle,1Max,1Min);

//數(shù)組后半部分的最小值與最大值

AtomicIntegerrMax=newAtomicInteger(0);

AtomicIntegerrMin=newAtomicInteger(0);

//數(shù)組后半部分的最大差值(第二種情況)

intrightMax=getMaxDiff(a,middle+1,end,rMax,rMin);

//對(duì)應(yīng)第三種情況

intmixMax=1Max.get()-rMin.get();

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

if(1Max.get()＞rMax.get())

max.set(1Max.get());

else

max.set(rMax.get());

if(1Min.get()＜rMin.get())

min.set(1Min.get());

else

min.set(rMin.get());

//求最大的差值

intallMax=(leftMax＞rightMax)?leftMax:rightMax;

allMax=(allMax＞mixMax)?allMax:mixMax;

returnallMax;

}

publicstaticvoidmain(String[]args){

int[]a={1,4,17,3,2,9};

System.out.println(getMax(a));

}

}

程序運(yùn)行結(jié)果為：

15

顯然，以上這種方法對(duì)數(shù)組只經(jīng)過(guò)一次遍歷，一次時(shí)間復(fù)雜度為O(n)，但是由于采用了遞歸的實(shí)現(xiàn)方式，在遞歸調(diào)用時(shí)要進(jìn)行壓棧與彈棧操作，因此有額外的開(kāi)銷(xiāo)，會(huì)導(dǎo)致算法性能有所下降。另外，在實(shí)現(xiàn)時(shí)，為了通過(guò)傳遞引用的方式獲取數(shù)組的最大值與最小值，使用了AtomicInteger而不是Integer類(lèi)。主要原因?yàn)镮nteger類(lèi)雖然也可以傳遞引用，但是它是不可變量，在方法內(nèi)部不能對(duì)其進(jìn)行修改。

方法三：動(dòng)態(tài)規(guī)劃。通過(guò)對(duì)題目進(jìn)行分析，發(fā)現(xiàn)這是一個(gè)非常典型的動(dòng)態(tài)規(guī)劃問(wèn)題，可以用動(dòng)態(tài)規(guī)劃的方法來(lái)求解。實(shí)現(xiàn)思路如下：給定數(shù)組a，申請(qǐng)額外的數(shù)組diff和max，其中diff[i]是以數(shù)組中第i個(gè)數(shù)字為減數(shù)的所有數(shù)對(duì)之差的最大值(前i+1個(gè)數(shù)組成的子數(shù)組中最大的差值)，max[i]為前i+1個(gè)數(shù)的最大值。假設(shè)已經(jīng)求得了diff[i]，diff[i+1]的值有兩種可能性：①等于diff[i]；②等于max[i]-a[i]。通過(guò)上面的分析，可以得到動(dòng)態(tài)規(guī)劃方法的計(jì)算表達(dá)式為：diff[i+1]=max(diff[i]，max[i-1]-a[i])，max[i+1]=max(max[i]，a[i+1])。數(shù)組最大的差值為diff[n-1](n為數(shù)組的長(zhǎng)度)。示例如下：

publicclassTest{

publicstaticintmax(intm,intn){

return(m＞n)?m:n;

}

publicstaticintgetMax(int[]a){

if(a==null)

returnInteger.MIN_VALUE;

intlen=a.length;

if(len＜=1)

returnInteger.MIN_VALUE;

int[]diff=Newint[len];

int[]max=newint[len];

diff[0]=0;

max[0]=a[0];

for(inti=1;i＜len;i++){

diff[i]=max(diff[i-1],max[i-1]-a[i]);

max[i]=max(max[i-1],a[i]);

}

returndiff[len-1];

}

publicstaticvoidmain(String[]args){

int[]a={1,4,17,3,2,9};

System.out.println(getMax(a));

}

}

程序運(yùn)行結(jié)果為：

15

以上這種方法也是對(duì)數(shù)據(jù)進(jìn)行了一次遍歷，因此時(shí)間復(fù)雜度為O(n)，由于沒(méi)有采用遞歸的方式，因此相比方法二，在性能上有所提升。由于引入了兩個(gè)額外的數(shù)組，因此這個(gè)算法的空間復(fù)雜度也為O(n)。

從動(dòng)態(tài)規(guī)劃方法的計(jì)算公式中可以看出，在求解diff[i+1]時(shí)，只用到了diff[i]與max[i]，而與數(shù)組diff和max中其他數(shù)字無(wú)關(guān)，因此可以通過(guò)兩個(gè)變量而不是數(shù)組來(lái)記錄diff[i]與max[i]的值，從而降低了算法的空間復(fù)雜度。示例如下：

publicclassTest{

publicstaticintmax(intm,intn){

return(m＞n)?m:n;

}

publicstaticintgetMax(int[]a){

if(a==null)

returnInteger.MIN_VALUE;

intlen=a.length;

if(len＜=1)

returnInteger.MIN_VALUE;

intdiff=0;

intmax=a[0];

for(inti=1;i＜len;i++){

diff=max(diff,max-a[i]);

max=max(max,a[i]);

}

returndiff;

}

publicstaticvoidmain(String[]args){

int[]a={1,4,17,3,2,9};

System.out.println(getMax(a));

}

}

引申：這道題還可以用求最大子數(shù)組之和的方法來(lái)解決嗎?

答案：可以。實(shí)現(xiàn)思路如下：給定一個(gè)數(shù)組a(數(shù)組長(zhǎng)度為n)，額外申請(qǐng)一個(gè)長(zhǎng)度為n-1的數(shù)組diff，數(shù)組diff中的值滿足diff[i]=a[i]-a[i+1]，那么a[i]-a[j](0＜i＜j＜n)就等價(jià)于diff[i]+diff[i+1]+…+diff[j]。因此，求所有a[i]-a[j]組合的最大值就可以轉(zhuǎn)換為求解所有diff[i]+diff[i+1]+…+diff[j]組合的最大值。由于diff[i]+diff[i+1]+…+diff[j]代表diff的一個(gè)子數(shù)組，因此可以用11.5.3節(jié)中求最大子數(shù)組之和的方法來(lái)解決。

9.

如何求絕對(duì)值最小的數(shù)正確答案：?jiǎn)栴}描述：有一個(gè)升序排列的數(shù)組，數(shù)組中可能有正數(shù)、負(fù)數(shù)或0，求數(shù)組中元素的絕對(duì)值最小的數(shù)，例如，數(shù)組{-10，-5，-2，7，15，50}，絕對(duì)值最小的是-2。

求絕對(duì)值最小的數(shù)可以分為3種情況：①如果數(shù)組第一個(gè)元素為非負(fù)數(shù)，那么絕對(duì)值最小的數(shù)肯定為數(shù)組的第一個(gè)元素；②如果數(shù)組最后一個(gè)元素為負(fù)數(shù)，那么絕對(duì)值最小的數(shù)肯定是數(shù)組的最后一個(gè)元素；③數(shù)組中即有正數(shù)又有負(fù)數(shù)時(shí)，首先找到正數(shù)與負(fù)數(shù)的分界點(diǎn)，如果分界點(diǎn)恰好為0，那么0就是絕對(duì)值最小的數(shù)，否則通過(guò)比較分界點(diǎn)左右的正數(shù)與負(fù)數(shù)的絕對(duì)值來(lái)確定最小的數(shù)。對(duì)于上面的例子來(lái)說(shuō)，正數(shù)與負(fù)數(shù)的分界點(diǎn)為-2和7。通過(guò)比較它們的絕對(duì)值從而確定-2的絕對(duì)值更小，因此-2就是要查找的數(shù)。

那么如何來(lái)查找正數(shù)與負(fù)數(shù)的分界點(diǎn)呢?最簡(jiǎn)單的方法仍然是順序遍歷數(shù)組，找出第一個(gè)非負(fù)數(shù)(前提是數(shù)組中既有正數(shù)又有負(fù)數(shù))，接著通過(guò)比較分界點(diǎn)兩個(gè)數(shù)的值來(lái)找出絕對(duì)值最小的數(shù)。這種方法在最壞的情況下時(shí)間復(fù)雜度為O(n)。下面主要介紹采用二分法來(lái)查找正數(shù)與負(fù)數(shù)的分界點(diǎn)的方法。其主要思路為：取數(shù)組中間位置的值a[mid]。①a[mid]=0，那么這個(gè)數(shù)就是絕對(duì)值最小的數(shù)；②a[mid]＞0，如果a[mid-1]＜0，那么就找到了分界點(diǎn)，通過(guò)比較a[mid]與a[mid-1]的絕對(duì)值就可以找到數(shù)組中絕對(duì)值最小的數(shù)，如果a[mid-1]=0，那么a[mid一1]就是要找的數(shù)，否則接著在數(shù)組的左半部分查找；③a[mid]＜0，如果a[mid+1]＞0，那么通過(guò)比較a[mid]與a[mid+1]的絕對(duì)值即可，如果a[mid+1]=0，那么a[mid+1]就是要查找的數(shù)，否則接著在數(shù)組的右半部分繼續(xù)查找。實(shí)現(xiàn)代碼如下：

publicclassTest{

publicstaticintgetMinAbsoluteValue(int[]a){

if(a==null)

returnInteger.MIN_VALUE;

intlen=a.length;

if(len＜1)

returnInteger.MIN_VALUE;

//數(shù)組中沒(méi)有負(fù)數(shù)

if(a[0]＞=0)

returna[0];

//數(shù)組中沒(méi)有正數(shù)

if(a[len-1]＜=0)

returna[len-1];

intmid=0;

intbegin=0;

intend=len-1;

intabsMin=0;

//數(shù)組中既有正數(shù)又有負(fù)數(shù)

while(true){

mid=begin+(end-begin)/2;

//如果值等于0，那么就是絕對(duì)值最小的數(shù)

if(a[mid]==0){

return0;

}//如果值大于0，那么正負(fù)數(shù)的分界點(diǎn)在左半部分

elseif(a[mid]＞0){

//繼續(xù)在數(shù)組的左半部分查找

if(a[mid-1]＞0)

end=mid-1;

elseif(a[mid-1]==0)

return0;

//找到正負(fù)數(shù)的分界點(diǎn)

else

break;

}//如果值小于0，在數(shù)組右半部分查找

else{

//在數(shù)組右半部分繼續(xù)查找

if(a[mid+1]＜0)

begin=mid+1;

elseif(a[mid+1]==0)

return0;

//找到正負(fù)數(shù)的分界點(diǎn)

else

break;

}

}

//獲取正負(fù)數(shù)分界點(diǎn)出絕對(duì)值最小的值

if(a[mid]＞0){

if(a[mid]＜Math.abs(a[mid-1]))

absMin=a[mid];

else

absMin=a[mid-1];

}else{

if(Math.abs(a[mid])＜a[mid+1])

absMin=a[mid];

else

absMin=a[mid+1];

}

returnabsMin;

}

publicstaticvoidmain(String[]args)throwsException{

int[]a1={-10,-5,-2,7,15,50};

int[]a2={2,4,6,8,27};

im[]a3={-13,-9,-7,-3};

intvalue=getMinAbsoluteValue(a1);

System.out.println(value);

value=getMinAhsoluteValue(a2);

System.out.println(value);

value=getMinAbsoluteValue(a3);

System.out.println(value);

}

}

程序運(yùn)行結(jié)果為：

-2

2

-3

10.

如何求數(shù)組中兩個(gè)元素的最小距離正確答案：?jiǎn)栴}描述：給定一個(gè)數(shù)組，數(shù)組中含有重復(fù)元素，給出兩個(gè)數(shù)n1和n2，求這兩個(gè)數(shù)字在數(shù)組中所出現(xiàn)位置的最小距離，例如，數(shù)組{4，5，6，4，7，4，6，4，7，8，5，6，4，3，10，8}中，4和8的最小距離為2。

實(shí)現(xiàn)思路如下：遍歷數(shù)組，會(huì)遇到以下兩種情況。

1)當(dāng)遇到n1時(shí)，記錄下n1值對(duì)應(yīng)的數(shù)組下標(biāo)的位置n1_index，通過(guò)求n1_index與上次遍歷到n2的下標(biāo)值n2_index的差，可以求出最近一次遍歷到的n1與n2的距離。

2)當(dāng)遇到n2時(shí)，同樣記錄下它在數(shù)組中下標(biāo)的位置n2_index，然后通過(guò)求n2_index與上次遍歷到n1的下標(biāo)值n1_index的差，求出最近一次遍歷到的n1與n2的距離。

定義一個(gè)變量min_dist記錄n1與n2的最小距離，在以上兩種情況下，每次求出n1與n2的距離后與min_dist相比，求最小值。這樣只需對(duì)數(shù)組進(jìn)行一次遍歷就可以求出最小距離，因此時(shí)間復(fù)雜度為O(n)。實(shí)現(xiàn)代碼如下：

publicclassTest{

privatestaticintmin(inta,intb){

returna＞b?b:a;

}

publicstaticintminDistance(inta[],intn1,intn2){

if(a==null)

returnInteger.MIN_VALUE;

intlen=a.length;

intn1_index=-1;

intn2_index=-1;

intmin_dist=Integer.MIN_VALUE+1;

for(inti=0;i＜len;++i){

if(a[i]==n1){

n1_index=i;

if(n2_index＞=0)

min_dist=min(Math.ahs(min_dist),Math.abs(n1_index-n2_index));}

if(a[i]==n2){

n2_index=i;

if(n1_index＞=0)

min_dist=min(Math.abs(min_dist),Math.abs(n2_index-n1_index));

}

}

returnmin_dist;

}

publicstaricvoidmain(String[]args){

inta[]={4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8};

System.out.println(minDistanee(a,4,8));

}

}

程序運(yùn)行結(jié)果為：

2

11.

如何求指定數(shù)字在數(shù)組中第一次出現(xiàn)的位置正確答案：?jiǎn)栴}描述：給定數(shù)組a={3，4，5，6，5，6，7，8，9，8}，這個(gè)數(shù)組中相鄰元素之差都為1，給定數(shù)字9，它在數(shù)組中第一次出現(xiàn)的位置的下標(biāo)為8(數(shù)組下標(biāo)從0開(kāi)始)。

方法一：“蠻力”法。假設(shè)指定數(shù)字為t順序遍歷數(shù)組中每一個(gè)元素，并且將數(shù)組中的元素與t進(jìn)行比較，判斷兩個(gè)值是否相等，若相等，則返回下標(biāo)位置；若遍歷完數(shù)組還沒(méi)找到t，則說(shuō)明t在數(shù)組中不存在，返回-1。該方法的時(shí)間復(fù)雜度為O(n)。

這種方法顯然沒(méi)有用到題目中“這個(gè)數(shù)組中相鄰元素之差的絕對(duì)值為1”這一條件，下面介紹一種更高效的方法。

方法二：跳躍搜索法。通過(guò)對(duì)數(shù)組中元素的特點(diǎn)進(jìn)行分析發(fā)現(xiàn)如下規(guī)律：假設(shè)先從數(shù)組a中查找9出現(xiàn)的位置，首先用數(shù)組中第一個(gè)元素(數(shù)組下標(biāo)為0)3與9進(jìn)行比較，它們的差值為6，由于數(shù)組中相鄰兩個(gè)元素的差值為1，因此9在數(shù)組中出現(xiàn)的最早的位置必定為：第1+6=7個(gè)位置(數(shù)組下標(biāo)為6)。這是因?yàn)椋喝绻麛?shù)組是遞增的，那么數(shù)組第7個(gè)元素的值才為9；如果數(shù)組不是遞增的，那么9出現(xiàn)的位置肯定在數(shù)組中第7個(gè)元素后面；上面的示例中待查找的數(shù)比數(shù)組中第一個(gè)元素的值大，對(duì)于待查找的數(shù)比數(shù)組中第一個(gè)元素小的情況，可以用相同的方法。根據(jù)這個(gè)特點(diǎn)可以得出算法的思路為：從數(shù)組第一個(gè)元素開(kāi)始(i=0)，把數(shù)組當(dāng)前位置的值與t進(jìn)行比較，如果相等，則返回?cái)?shù)組下標(biāo)，否則，從數(shù)組下標(biāo)為i+|t-a[i]|處繼續(xù)查找。實(shí)現(xiàn)代碼如下：

publicclassTest{

publicstaticintfindIndex(inta[],intt){

if(a==null)

return;

intlen=a.length;

inti=0;

while(i＜len){

if(a[i]==t){

returni;

}else{

i+=Math.abs(t-a[i]);

}

}

return-1;

}

publicstaticvoidmain(String[]args){

inta[]={3,4,5,6,5,6,7,8,9,8};

System.out.println(findIndex(a,9));

}

}

程序運(yùn)行結(jié)果為：

8

顯然，采用以上跳躍搜索法減：少了對(duì)數(shù)組中元素的訪問(wèn)個(gè)數(shù)，從而提高了算法的效率。

12.

如何對(duì)數(shù)組的兩個(gè)子有序段進(jìn)行合并正確答案：?jiǎn)栴}描述：數(shù)組a[0，mid-1]和a[mid，n-1]是各自有序的，對(duì)數(shù)組a[0，n-1]的兩個(gè)子有序段進(jìn)行合并，得到a[0，n-1]整體有序。要求空間復(fù)雜度為O(1)(注：al[i]元素是支持'＜'運(yùn)算符的)。假設(shè)給定數(shù)組a={1，5，6，7，9，2，4，8，10，13，14}，mid=5，a[0]～a[4]是有序的，a[5]～a[10]是有序的，合并后的數(shù)組為{1，2，4，5，6，7，8，9，10，13，14}。

假設(shè)數(shù)組中的兩個(gè)子有序段都按升序排列，如上例所示。下面給出在這種情況下的實(shí)現(xiàn)思路。

由于限定空間復(fù)雜度為O(1)，因此不能使用歸并方法。最容易想到的就是插入排序方法，這種算法的時(shí)間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(1)，能滿足題目要求，但是由于插入排序方法沒(méi)有用到“數(shù)組a[0，mid-1]和a[mid，num-1]是各自有序的”這個(gè)條件，因此這種算法肯定不是最好的算法，下面給出另外一種方法。

實(shí)現(xiàn)思路：首先，遍歷數(shù)組中下標(biāo)為0～mid-1的元素，將遍歷到的元素的值與a[mid]進(jìn)行比較，當(dāng)遍歷到a[i](0＜=i＜=mid-1)時(shí)，如果滿足a[mid]＜a[i]，那么交換a[i]與a[mid]的值。接著找到交換后的a[mid]在a[mid，num-1]中的具體位置(在a[mid，num-1]中進(jìn)行插入排序)，實(shí)現(xiàn)方法為：遍歷a[mid～num-2]，如果a[mid+1]＜a[mid]，那么交換a[mid]與a[mid+1]的位置。實(shí)現(xiàn)代碼如下：

publicclassTest{

publicstaticvoidfindRightPlaceForMid(inta[],intmid){

intlen=a.length;

inttmp;

for(inti=mid;i＜len-1;i++){

if(a[i+1]＜a[i]){

tmp=a[i];

a[i]=a[i+1];

a[i+1]=tmp;

}

}

}

publicstaticvoidsort(inta[],intmid){

inttmp;

for(inti=0;i＜=mid-1;i++){

if(a[mid]＜a[i]){

tmp=a[i];

a[i]=a[mid];

a[mid]=tmp;

findRightPlaceForMid(a,mid);

}

}

}

publicstaticvoidmain(String[]args){

inta[]={1,5,6,7,9,2,4,8,10,13,14};

sort(a,5);

fnr(inti=0;i＜11;i++)

System.out.print(a[i]+"");

}

}

程序運(yùn)行結(jié)果為：

12456789101314

在實(shí)現(xiàn)時(shí)需要注意的問(wèn)題是：題目中給出了“al[i]元素是支持＜'運(yùn)算符的”這一限制條件，因此，在程序中只能出現(xiàn)形如“a[i]＜a[j]”的表達(dá)式，最好不要出現(xiàn)“a[j]＞a[i]”這種寫(xiě)法。

引申：

1)如果數(shù)組中兩個(gè)子有序段都按降序排列，可以用類(lèi)似的方法來(lái)解決。

2)如果其中一個(gè)子序段按升序排列，另外一個(gè)子序段按降序排列，可以首先對(duì)其中一個(gè)子序段進(jìn)行逆序，然后采用上面介紹的方法進(jìn)行排序。

13.

如何計(jì)算兩個(gè)有序整型數(shù)組的交集正確答案：假設(shè)兩個(gè)含有n個(gè)元素的有序(非降序)整型數(shù)組a和b，其中a={0，1，2，3，4}，b={1，3，5，7，9}，那么它們的交集為{1，3}。

計(jì)算數(shù)組交集可以采用很多種方法，但數(shù)組的相對(duì)大小一般會(huì)影響算法的效率，所以需要根據(jù)兩個(gè)數(shù)組的相對(duì)大小來(lái)確定采用的方法：

1)對(duì)于兩個(gè)數(shù)組長(zhǎng)度相當(dāng)?shù)那闆r，一般可以采取如下3種方法。

方法一：二路歸并法。設(shè)兩個(gè)數(shù)組分別為array1[n1]和array2[n2]。分別以i，j從頭開(kāi)始遍歷兩個(gè)數(shù)組。在遍歷過(guò)程中，若當(dāng)前遍歷位置的array1[i]與array2[j]相等，則此數(shù)為兩個(gè)數(shù)組的交集，記錄下來(lái)，并繼續(xù)向后遍歷array1和array2。若array1[i]大于array2[j]，則須繼續(xù)向后遍歷array2。若array1[i]小于array2[j]，則需要繼續(xù)向后遍歷array1，直到有一個(gè)數(shù)組結(jié)束遍歷即停止。實(shí)現(xiàn)代碼如下：

importjava.util.*;

publicclassTest{

publicstaticArrayList＜Integer＞mixed(intarray1[],intarray2[]){

ArrayList＜Integer＞mix=newArrayList＜Integer＞();

inti=0,j=0;

intn1=array1.length;

intn2=array2.length;

while(i＜n1&&j＜n2){

if(array1[i]==array2[j]){

mix.add(array1[i]);

i++;

j++;

}elseif(array1[i]＞array2[j]){

j++;

}elseif(array1[i]＜array2[j]){

i++;

}

}

returnmix;

}

publicstaticvoidmain(String[]args){

int[]a={0,1,2,3,4};

int[]b={1,3,5,7,9};

ArrayList＜Integer＞mix=mixed(a,b);

for(inti=0;i＜mix.size();i++)

System.out.print(mix.get(i)+"");

}

}

程序運(yùn)行結(jié)果為：

13

方法二：順序遍歷法。順序遍歷兩個(gè)數(shù)組，將數(shù)組元素存放到哈希表中，同時(shí)對(duì)統(tǒng)計(jì)的數(shù)組元素進(jìn)行計(jì)數(shù)，若為2，則為二者的交集元素。

方法三：散列法。遍歷兩個(gè)數(shù)組中任意一個(gè)數(shù)組，將遍歷得到的元素存放到散列表，然后遍歷另外一個(gè)數(shù)組，同時(shí)對(duì)建立的散列表進(jìn)行查詢，若存在，則為交集元素。

2)對(duì)于兩個(gè)數(shù)組長(zhǎng)度相差懸殊的情況，例如，數(shù)組a的長(zhǎng)度遠(yuǎn)遠(yuǎn)大于數(shù)組b的長(zhǎng)度，則可以采用下面幾種方法。

方法一：依次遍歷長(zhǎng)度短的數(shù)組，將遍歷得到的數(shù)組元素在長(zhǎng)數(shù)組中進(jìn)行二分查找。具體而言，設(shè)兩個(gè)指向兩個(gè)數(shù)組末尾元素的指針，取較小的那個(gè)數(shù)在另一個(gè)數(shù)組中二分查找，找到，則存在一個(gè)交集，并且將該目標(biāo)數(shù)組的指針指向該位置的前一個(gè)位置。如果沒(méi)有找到，同樣可以找到一個(gè)位置，使得目標(biāo)數(shù)組中在該位置后的數(shù)肯定不在另一個(gè)數(shù)組中存在，直接移動(dòng)該目標(biāo)數(shù)組的指針指向該位置的前一個(gè)位置，再循環(huán)找，直到一個(gè)數(shù)組為空為止。由于兩個(gè)數(shù)組中都可能出現(xiàn)重復(fù)的數(shù)，因此二分查找時(shí)，當(dāng)找到一個(gè)相同的數(shù)x時(shí)，其下標(biāo)為i，那么下一個(gè)二分查找的下界變?yōu)閕+1，避免x重復(fù)使用。

方法二：采用與方法一類(lèi)似的方法，但是每次查找在前一次查找的基礎(chǔ)上進(jìn)行，這樣可以大大縮小查找表的長(zhǎng)度。

方法三：采用與方法二類(lèi)似的方法，但是遍歷長(zhǎng)度小的數(shù)組的方式有所不同，即從數(shù)組頭部和尾部同時(shí)開(kāi)始遍歷，這樣可以進(jìn)一步縮小查找表的長(zhǎng)度。

14.

如何判斷一個(gè)數(shù)組中數(shù)值是否連續(xù)相鄰正確答案：一個(gè)數(shù)組序列，元素取值可能是0～65535中的任意一個(gè)數(shù)，相同數(shù)值不會(huì)重復(fù)出現(xiàn)。0是例外，可以反復(fù)出現(xiàn)。設(shè)計(jì)一種算法，當(dāng)從該數(shù)組序列中隨意選取5個(gè)數(shù)值，判斷這5個(gè)數(shù)值是否連續(xù)相鄰。需要注意以下4點(diǎn)：

1)5個(gè)數(shù)值允許是亂序的，例如{8，7，5，0，6}。

2)0可以通配任意數(shù)值，例如{8，7，5，0，6}中的0可以通配成9或者4。

3)0可以多次出現(xiàn)。

4)全0算連續(xù)，只有一個(gè)非0算連續(xù)。

如果沒(méi)有0的存在，要組成連續(xù)的數(shù)列，最大值和最小值的差距必須是4，存在0的情況下，只要最大值和最小值的差距小于4就可以了，所以應(yīng)找出數(shù)列中非0的最大值和非0的最小值，時(shí)間復(fù)雜度為O(n)，如果非0最大-非0最小+1＜=5(即非0最大-非0最?。?4)，那么這5個(gè)數(shù)值連續(xù)相鄰，否則，不連續(xù)相鄰。因此，該算法的時(shí)間復(fù)雜度為O(n)。

程序代碼如下：

publicclassTest{

publicstaticBooleanIsContinuous(int[]a){

intn=a.length;

intmin=-1,max=-1;

for(inti=0;i＜n;i++){

if(a[i]!=0){

if(min＞a[i]||-1==min)

min=a[i];

if(mox＜a[i]||-1==max)

max=a[i];

}

}

if(max-min＞n-1)

returnfalse;

else

returntrue;

}

publicstaticvoidmain(String[]args){

intarray[]={8,7,5,0,6};

if(IsContinuous(array))

System.out.println("數(shù)組{8,7,5,0,6}連續(xù)相鄰\n");

else

System.out.println("數(shù)組{8,7,5,0,6}不連續(xù)相鄰");

}

}

程序運(yùn)行結(jié)果為：

8,7,5,0,6連續(xù)相鄰

15.

如何求解數(shù)組中反序?qū)Φ膫€(gè)數(shù)正確答案：?jiǎn)栴}描述：給定一個(gè)數(shù)組a，如果a[i]＞a[j](i＜j)，那么a[i]與a[j]被稱為一個(gè)反序，例如，給定數(shù)組{1，5，3，2，6}，共有(5，3)、(5，2)和(3，2)三個(gè)反序?qū)Α?/p>

方法一：“蠻力”法。最容易想到的方法是對(duì)數(shù)組中的每一個(gè)數(shù)字，遍歷它后面的所有數(shù)字，如果后面的數(shù)字比它小，那么就找到一個(gè)逆序?qū)Γ瑢?shí)現(xiàn)代碼如下：

publicclassTest{

publicstaticintreverseCount(inta[]){

intcount=0;

intlen=a.length;

for(inti=0;i＜len;i++){

for(intj=i+1;j＜len;j++){

if(a[i]＞a[j]){

count++;

}

}

}

returncount;

}

publicstaticvoidmain(String[]args){

intarray[]={1,5,3,2,6};

intcount=reverseCount(array);

System.out.println(count);

}

}

程序運(yùn)行結(jié)果為：

3

這種方法是采用二重遍歷實(shí)現(xiàn)的，因此時(shí)間復(fù)雜度為O(n^2)。

方法二：分治歸并法。可以參：考?xì)w并排序的方法，在歸并排序的基礎(chǔ)上額外使用一個(gè)計(jì)數(shù)器來(lái)記錄逆序?qū)Φ膫€(gè)數(shù)。下面以數(shù)組序列{5，8，3，6}為例，說(shuō)明計(jì)數(shù)的方法，歸并的過(guò)程如下所示。

示例如下：

publicclassTest{

publicstaticintreverseCount=0;

publicstaticvoidmerge(intarray[],intbegin,intmid,intend){

inti,j,k,n1,n2;

n1=mid-begin+1;

n2=end-mid;

int[]L=newint[n1];

int[]R=newint[n2];

for(i=0,k=begin;i＜n1;i++,k++)

L[i]=array[k];

for(i=0,k=mid+1;i＜n2;i++,k++)

R[i]=array[k];

for(k=begin,i=0,j=0;i＜n1&&j＜n2;k++){

if(L[i]＜R[j]){

array[k]=L[i++];

}else{

reverseCount+=mid-i+1;

array[k]=R[j++];

}

}

if(i＜n1){

for(j=i;j＜n1;j++,k++)

array[k]=L[j];

}

if(j＜n2){

for(i=j;i＜n2;i++,k++)

array[k]=R[i];

}

}

publicstaticvoidmerge_sort(inta[],intbegin,intend){

if(begin＜end){

intmid=(end+begin)/2;

merge_sort(a,begin,mid);

merge_sort(a,mid+1,end);

merge(a,begin,mid,end);

}

}

publicstaticvoidmain(String[]args){

intarray[]={1,5,3,2,6};

merge_sort(array,0,array.length-1);

System.out.println(reverseCount);

}

}

程序運(yùn)行結(jié)果為：

3

這種方法與歸并排序有著相同的時(shí)間復(fù)雜度O(nlogn)。

16.

如何求解最小三元組距離正確答案：?jiǎn)栴}描述：已知3個(gè)升序整數(shù)數(shù)組a[1]、b[m]和c[n]。請(qǐng)?jiān)?個(gè)數(shù)組中各找一個(gè)元素，使得組成的三元組距離最小。三元組的距離定義是：假設(shè)a[i]、b[j]和c[k]是一個(gè)三元組，那么距離為Distance=max(|a[i]-b[j]|，|a[i]-c[k]|，|b[j]-c[k]|)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)求最小三元組距離的最優(yōu)算法。

方法一：“蠻力”法。最容易想到的方法就是分別遍歷3個(gè)數(shù)組中的元素，分別求出它們的距離，然后從這些值里面查找最小值，示例如下：

publicclassTest{

publicstaticintmax(inta,intb,intc){

intmax=a＜b?b:a;

max=max＜c?c:max;

returnmax;

}

publicstaticintSolvingviolence(inta[],intb[],intc[]){

intaLen=a.length;

intbLen=b.length;

intcLen=c.length;

intminDist=max(Math.abs(a[0]-b[0]),Math.abs(a[0]-c[0]),Math.abs(b[0]-

c[0]));

intdist=0;

for(inti=0;i＜aLen;i++){

for(intj=0;j＜bLen;j++){

for(intk=0;k＜cLen;k++){

//求距離

dist=max(Math.abs(a[i]-b[j]),Math.abs(a[i]-c[k]),

Math.abs(b[j]-c[k]));

//找出最小距離

if(minDist＞dist){

minDist=dist;

}

}

}

}

returnminDist;

}

publicstaticvoidmain(String[]args){

inta[]={3,4,5,7};

intb[]={10,12,14,1,5,17};

intc[]={20,21,23,24,37,30};

System.out.println(Solvingviolence(a,b,c));

}

}

這個(gè)算法的時(shí)間復(fù)雜度為O(1*m*n)，顯然這個(gè)方法沒(méi)有用到數(shù)組升序這一特性，因此不是最好的方法。

方法二：最小距離法。假設(shè)當(dāng)前遍歷到這3個(gè)數(shù)組中的元素分別為ai，bi，ci，并且ai＜=bi＜=ci，此時(shí)它們的距離肯定為Di=ci-ai，那么可以分如下3種情況討論：

1)如果接下來(lái)求ai，bi，ci+1的距離，那么由于ci+1＞=ci，此時(shí)它們的距離必定為Di+1=ci+1-ai，顯然Di+1＞=Di，因此Di+1不可能為最小距離。

2)如果接下來(lái)