Java程序員面試分類模擬16

Java程序員面試分類模擬16論述題1.

如何找出數(shù)組中重復(fù)元素最多的數(shù)正確答案：問題描述：對于數(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ù)。

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

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

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

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

importjava.util.*;

publicclassTest{

publicstaticintfindMostFrequentInArray(int[]a){

intresult=0;

intsize=a.length;

if(size==0)

returnInteger.MAX_VALUE;

//記錄每個元素出現(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);

}

}

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

6

2.

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

方法一：“蠻力”法

最容易想到的方法就是采用兩重循環(huán)遍歷數(shù)組來判斷兩個數(shù)的和是否為20。實現(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);

}

}

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

17,3

6,14

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

方法二：排序法

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

}

}

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

3,17

6,14

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

3.

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

}

}

}

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

78123456

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

4.

如何找出數(shù)組中第k個最小的數(shù)正確答案：問題描述：給定一個無序的數(shù)組，從一個數(shù)組中找出第k個最小的數(shù)，例如，對于給定數(shù)組序列{1，5，2，6，8，0，6}，其中第4小的數(shù)為5。

方法一：排序法

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

方法二：“剪枝”法

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

}

}

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

5

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

5.

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

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

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

}

}

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

5

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

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

publicclassTest{

publicstaticintfindOnee(inta[],intappearTimes){

intn=a.length;

int[]bitCount=newint[32];

//計算數(shù)組中所有數(shù)組對應(yīng)的二進制數(shù)各個位置上出現(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);

}

}

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

3

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

6.

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

由于題目要求每個數(shù)組元素只能訪問1次，且不用輔助存儲空間，因此可以從原理上入手，采用數(shù)學(xué)求和法，因為只有一個數(shù)字重復(fù)1次，而又是連續(xù)的，根據(jù)累加和原理，對數(shù)組的所有項求和，然后減去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);

}

}

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

1

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

(1)異或法

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

設(shè)重復(fù)數(shù)為A，其余N-2個數(shù)異或結(jié)果為B，N個數(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);

}

}

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

1

(2)空間換時間法

申請長度為N-1的整型數(shù)組flag并初始化為0，然后從頭開始遍歷數(shù)組a，取每個數(shù)組元素a[i]的值，將其對應(yīng)的數(shù)組flag中的元素賦值為1，如果已經(jīng)置過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);

}

}

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

1

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

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

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

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

以上提出的兩種方案都需要額外的存儲空間，能否不使用額外存儲空間呢?答案是可以。于是想到了方案三：取反法。取反：去的基本思路如下：如果遍歷到數(shù)組中的元素為i，那么把a[i]的值取反，如果i在數(shù)組中出現(xiàn)兩次，那么a[i]會經(jīng)過兩次取反操作，a[i]的值跟原始的值相等，且為正數(shù)；如果i出現(xiàn)了1次，那么a[i]的值為原始值的相反數(shù)，且為負數(shù)，可以根據(jù)這個原理來實現(xiàn)。實現(xiàn)方法如下：將數(shù)組元素值作為索引，對于元素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ù)組第二個元素開始遍歷數(shù)組，如果array[i]＞0，那么這個數(shù)就是重復(fù)的。由于在進行遍歷后對數(shù)組中的數(shù)據(jù)進行了修改，因此需要對數(shù)據(jù)進行還原(對數(shù)組中的負數(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);

}

}

方法四是一種非?！霸幃悺钡乃惴ǎ褪遣捎妙愃朴趩捂湵硎欠翊嬖诃h(huán)的問題?！芭袛鄦捂湵硎欠翊嬖诃h(huán)”是一個非常經(jīng)典的問題，同時單鏈表可以采用數(shù)組實現(xiàn)，此時每個元素值作為next指針指向下一個元素。本題可以轉(zhuǎn)化為“已知一個單鏈表中存在環(huán)，找出環(huán)的入口點”這種想法。具體思路如下：將array[i]看作第i個元素的索引，即array[i]→array[array[i]]→array[array[array[i]]]→array[array[array[array[i]]]]→…，最終形成一個單鏈表，由于數(shù)組a中存在重復(fù)元素，因此一定存在一個環(huán)，且環(huán)的入口元素即為重復(fù)元素。

該題的關(guān)鍵在于，數(shù)組array的長度是n，而元素的范圍是[1，n-1]，所以array[0]不會指向自己，進而不會陷入錯誤的自循環(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)中的一個點

x=0;

do{

x=a[x];

y=a[y];

}while(x!=y);

//找到入口點

returnx;

}

publicstaticvoidmain(String[]args){

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

intmissingNum=findInteger(a);

System.out.println(missingNum);

}

}

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

1

7.

如何用遞歸方法求一個整數(shù)數(shù)組的最大元素正確答案：對于本題而言，最容易實現(xiàn)的方法為對數(shù)組進行遍歷，定義一個變量max為數(shù)組的第一個元素，然后從第二個元素開始遍歷，在遍歷過程中，每個元素都與max的值進行比較，若該元素的值比max的值大，則把該元素的值賦給max。當(dāng)遍歷完數(shù)組后，最大值也就求出來了。而使用遞歸方法求解的主要思路為：遞歸的求解“數(shù)組第一個元素”與“數(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));

}

}

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

16

8.

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

方法一：“蠻力”法?！靶U力”法也是最容易想到的方法，其原理如下：首先，遍歷數(shù)組，找到所有可能的差值；其次，從所有差值中找出最大值。具體實現(xiàn)方法為：針對數(shù)組a中的每個元素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));

}

}

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

15

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

方法二：二分法。通過二分法可以減少計算的次數(shù)。思路如下：把數(shù)組分為兩個子數(shù)組，那么最大的差值只能有3種可能：①最大的差值對應(yīng)的被減數(shù)和減數(shù)都在左子數(shù)組中，假設(shè)最大差值為leftMax；②被減數(shù)和減數(shù)都在右子數(shù)組中，假設(shè)最大差值為rightMax；③被減數(shù)是左子數(shù)組的最大值，減數(shù)是右子數(shù)組中的最小值，假設(shè)差值為mixMax。那么就可以得到這個數(shù)組的最大差值為這3個差值的最大值，即max(leftMax，rightNax，mixMax)。實現(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);

//對應(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));

}

}

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

15

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

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

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

}

}

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

15

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

從動態(tài)規(guī)劃方法的計算公式中可以看出，在求解diff[i+1]時，只用到了diff[i]與max[i]，而與數(shù)組diff和max中其他數(shù)字無關(guān)，因此可以通過兩個變量而不是數(shù)組來記錄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ù)組之和的方法來解決嗎?

答案：可以。實現(xiàn)思路如下：給定一個數(shù)組a(數(shù)組長度為n)，額外申請一個長度為n-1的數(shù)組diff，數(shù)組diff中的值滿足diff[i]=a[i]-a[i+1]，那么a[i]-a[j](0＜i＜j＜n)就等價于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的一個子數(shù)組，因此可以用11.5.3節(jié)中求最大子數(shù)組之和的方法來解決。

9.

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

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

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

publicclassTest{

publicstaticintgetMinAbsoluteValue(int[]a){

if(a==null)

returnInteger.MIN_VALUE;

intlen=a.length;

if(len＜1)

returnInteger.MIN_VALUE;

//數(shù)組中沒有負數(shù)

if(a[0]＞=0)

returna[0];

//數(shù)組中沒有正數(shù)

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

returna[len-1];

intmid=0;

intbegin=0;

intend=len-1;

intabsMin=0;

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

while(true){

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

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

if(a[mid]==0){

return0;

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

elseif(a[mid]＞0){

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

if(a[mid-1]＞0)

end=mid-1;

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

return0;

//找到正負數(shù)的分界點

else

break;

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

else{

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

if(a[mid+1]＜0)

begin=mid+1;

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

return0;

//找到正負數(shù)的分界點

else

break;

}

}

//獲取正負數(shù)分界點出絕對值最小的值

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

}

}

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

-2

2

-3

10.

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

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

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

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

定義一個變量min_dist記錄n1與n2的最小距離，在以上兩種情況下，每次求出n1與n2的距離后與min_dist相比，求最小值。這樣只需對數(shù)組進行一次遍歷就可以求出最小距離，因此時間復(fù)雜度為O(n)。實現(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));

}

}

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

2

11.

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

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

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

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

}

}

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

8

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

12.

如何對數(shù)組的兩個子有序段進行合并正確答案：問題描述：數(shù)組a[0，mid-1]和a[mid，n-1]是各自有序的，對數(shù)組a[0，n-1]的兩個子有序段進行合并，得到a[0，n-1]整體有序。要求空間復(fù)雜度為O(1)(注：al[i]元素是支持'＜'運算符的)。假設(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ù)組中的兩個子有序段都按升序排列，如上例所示。下面給出在這種情況下的實現(xiàn)思路。

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

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

}

}

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

12456789101314

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

引申：

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

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

13.

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

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

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

方法一：二路歸并法。設(shè)兩個數(shù)組分別為array1[n1]和array2[n2]。分別以i，j從頭開始遍歷兩個數(shù)組。在遍歷過程中，若當(dāng)前遍歷位置的array1[i]與array2[j]相等，則此數(shù)為兩個數(shù)組的交集，記錄下來，并繼續(xù)向后遍歷array1和array2。若array1[i]大于array2[j]，則須繼續(xù)向后遍歷array2。若array1[i]小于array2[j]，則需要繼續(xù)向后遍歷array1，直到有一個數(shù)組結(jié)束遍歷即停止。實現(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)+"");

}

}

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

13

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

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

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

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

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

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

14.

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

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

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

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

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

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

}

}

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

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

15.

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

方法一：“蠻力”法。最容易想到的方法是對數(shù)組中的每一個數(shù)字，遍歷它后面的所有數(shù)字，如果后面的數(shù)字比它小，那么就找到一個逆序?qū)?，實現(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);

}

}

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

3

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

方法二：分治歸并法?？梢詤ⅲ嚎細w并排序的方法，在歸并排序的基礎(chǔ)上額外使用一個計數(shù)器來記錄逆序?qū)Φ膫€數(shù)。下面以數(shù)組序列{5，8，3，6}為例，說明計數(shù)的方法，歸并的過程如下所示。

示例如下：

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

}

}

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

3

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

16.

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

方法一：“蠻力”法。最容易想到的方法就是分別遍歷3個數(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));

}

}

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

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

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

2)如果接下來