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

如何找出數組中重復元素最多的數正確答案：問題描述：對于數組{1，1，2，2，4，4，4，4，5，5，6，6，6}，元素1出現的次數為2次，元素2出現的次數（江南博哥）為2次，元素4出現的次數為4次，元素5出現的次數為2次，元素6出現的次數為3次，找出數組中出現重復次數最多的數。

上述問題中，程序的輸出應該為元素4。

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

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

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

importjava.util.*;

publicclassTest{

publicstaticintfindMostFrequentInArray(int[]a){

intresult=0;

intsize=a.length;

if(size==0)

returnInteger.MAX_VALUE;

//記錄每個元素出現的次數

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

}

}

//找出出現次數最多的元素

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

}

}

程序運行結果為：

6

2.

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

方法一：“蠻力”法

最容易想到的方法就是采用兩重循環遍歷數組來判斷兩個數的和是否為20。實現代碼如下：

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

}

}

程序運行結果為：

17,3

6,14

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

方法二：排序法

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

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

}

}

程序運行結果為：

3,17

6,14

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

3.

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

1)逆序數組子序列123456，數組序列的形式變為65432178。

2)逆序數組子序列78，數組序列的形式變為65432187。

3)全部逆序，數組序列的形式變為78123456。

程序代碼如下：

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位的結果是一樣的

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]+"");

}

}

}

程序運行結果如下：

78123456

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

4.

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

方法一：排序法

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

方法二：“剪枝”法

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

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

}

}

程序運行結果為：

5

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

5.

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

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

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

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

}

}

程序運行結果為：

5

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

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

publicclassTest{

publicstaticintfindOnee(inta[],intappearTimes){

intn=a.length;

int[]bitCount=newint[32];

//計算數組中所有數組對應的二進制數各個位置上出現1的次數

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

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

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

//若某位上的結果不能被整除，則肯定目標數字在這一位上

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

}

}

程序運行結果為：

3

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

6.

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

由于題目要求每個數組元素只能訪問1次，且不用輔助存儲空間，因此可以從原理上入手，采用數學求和法，因為只有一個數字重復1次，而又是連續的，根據累加和原理，對數組的所有項求和，然后減去1～N-1的和，即為所求的重復數。示例如下：

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

}

}

程序運行結果為：

1

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

(1)異或法

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

設重復數為A，其余N-2個數異或結果為B，N個數異或結果為A^A^B，1～N-1異或結果為A^B，由于異或滿足交換律和結合律，且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);

}

}

程序運行結果為：

1

(2)空間換時間法

申請長度為N-1的整型數組flag并初始化為0，然后從頭開始遍歷數組a，取每個數組元素a[i]的值，將其對應的數組flag中的元素賦值為1，如果已經置過1，那么該數就是重復的數。示例如下：

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

}

}

程序運行結果為：

1

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

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

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

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

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

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

}

}

方法四是一種非常“詭異”的算法，就是采用類似于單鏈表是否存在環的問題。“判斷單鏈表是否存在環”是一個非常經典的問題，同時單鏈表可以采用數組實現，此時每個元素值作為next指針指向下一個元素。本題可以轉化為“已知一個單鏈表中存在環，找出環的入口點”這種想法。具體思路如下：將array[i]看作第i個元素的索引，即array[i]→array[array[i]]→array[array[array[i]]]→array[array[array[array[i]]]]→…，最終形成一個單鏈表，由于數組a中存在重復元素，因此一定存在一個環，且環的入口元素即為重復元素。

該題的關鍵在于，數組array的長度是n，而元素的范圍是[1，n-1]，所以array[0]不會指向自己，進而不會陷入錯誤的自循環。如果元素的范圍中包含0，那么該題不可直接采用該方法。示例如下：

publicclassTest1{

publicstaticintfindInteger(inta[]){

intx,y;

x=y=0;

do{

x=a[a[x]];

//x一次走兩步

y=a[y];

//y一次走一步

}while(x!=y);

//找到環中的一個點

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

}

}

程序運行結果為：

1

7.

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

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

}

}

程序運行結果為：

16

8.

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

方法一：“蠻力”法。“蠻力”法也是最容易想到的方法，其原理如下：首先，遍歷數組，找到所有可能的差值；其次，從所有差值中找出最大值。具體實現方法為：針對數組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));

}

}

程序運行結果為：

15

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

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

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;

//數組前半部分的最小值與最大值

AtomicIntegerlMax=newAtomicInteger(0);

AtomicIntegerlMin=newAtomicInteger(0);

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

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

//數組后半部分的最小值與最大值

AtomicIntegerrMax=newAtomicInteger(0);

AtomicIntegerrMin=newAtomicInteger(0);

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

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

//對應第三種情況

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

//求數組的最大值與最小值

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

}

}

程序運行結果為：

15

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

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

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

}

}

程序運行結果為：

15

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

從動態規劃方法的計算公式中可以看出，在求解diff[i+1]時，只用到了diff[i]與max[i]，而與數組diff和max中其他數字無關，因此可以通過兩個變量而不是數組來記錄diff[i]與max[i]的值，從而降低了算法的空間復雜度。示例如下：

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

}

}

引申：這道題還可以用求最大子數組之和的方法來解決嗎?

答案：可以。實現思路如下：給定一個數組a(數組長度為n)，額外申請一個長度為n-1的數組diff，數組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]組合的最大值就可以轉換為求解所有diff[i]+diff[i+1]+…+diff[j]組合的最大值。由于diff[i]+diff[i+1]+…+diff[j]代表diff的一個子數組，因此可以用11.5.3節中求最大子數組之和的方法來解決。

9.

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

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

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

publicclassTest{

publicstaticintgetMinAbsoluteValue(int[]a){

if(a==null)

returnInteger.MIN_VALUE;

intlen=a.length;

if(len＜1)

returnInteger.MIN_VALUE;

//數組中沒有負數

if(a[0]＞=0)

returna[0];

//數組中沒有正數

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

returna[len-1];

intmid=0;

intbegin=0;

intend=len-1;

intabsMin=0;

//數組中既有正數又有負數

while(true){

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

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

if(a[mid]==0){

return0;

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

elseif(a[mid]＞0){

//繼續在數組的左半部分查找

if(a[mid-1]＞0)

end=mid-1;

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

return0;

//找到正負數的分界點

else

break;

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

else{

//在數組右半部分繼續查找

if(a[mid+1]＜0)

begin=mid+1;

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

return0;

//找到正負數的分界點

else

break;

}

}

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

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

}

}

程序運行結果為：

-2

2

-3

10.

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

實現思路如下：遍歷數組，會遇到以下兩種情況。

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

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

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

}

}

程序運行結果為：

2

11.

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

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

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

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

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

}

}

程序運行結果為：

8

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

12.

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

假設數組中的兩個子有序段都按升序排列，如上例所示。下面給出在這種情況下的實現思路。

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

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

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]+"");

}

}

程序運行結果為：

12456789101314

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

引申：

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

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

13.

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

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

1)對于兩個數組長度相當的情況，一般可以采取如下3種方法。

方法一：二路歸并法。設兩個數組分別為array1[n1]和array2[n2]。分別以i，j從頭開始遍歷兩個數組。在遍歷過程中，若當前遍歷位置的array1[i]與array2[j]相等，則此數為兩個數組的交集，記錄下來，并繼續向后遍歷array1和array2。若array1[i]大于array2[j]，則須繼續向后遍歷array2。若array1[i]小于array2[j]，則需要繼續向后遍歷array1，直到有一個數組結束遍歷即停止。實現代碼如下：

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

}

}

程序運行結果為：

13

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

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

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

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

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

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

14.

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

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

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

3)0可以多次出現。

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

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

else

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

}

}

程序運行結果為：

8,7,5,0,6連續相鄰

15.

如何求解數組中反序對的個數正確答案：問題描述：給定一個數組a，如果a[i]＞a[j](i＜j)，那么a[i]與a[j]被稱為一個反序，例如，給定數組{1，5，3，2，6}，共有(5，3)、(5，2)和(3，2)三個反序對。

方法一：“蠻力”法。最容易想到的方法是對數組中的每一個數字，遍歷它后面的所有數字，如果后面的數字比它小，那么就找到一個逆序對，實現代碼如下：

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

}

}

程序運行結果為：

3

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

方法二：分治歸并法。可以參：考歸并排序的方法，在歸并排序的基礎上額外使用一個計數器來記錄逆序對的個數。下面以數組序列{5，8，3，6}為例，說明計數的方法，歸并的過程如下所示。

示例如下：

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

}

}

程序運行結果為：

3

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

16.

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

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

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

}

}

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

方法二：最小距離法。假設當前遍歷到這3個數組中的元素分別為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)如果接下來