一個含有多個元素的數組，有多種排序方式。它可以升序排列，可以降序排列，也可以像我們以前章節說過的，以波浪形方式排序，現在我們要看到的一種是絕對值排序。對於數組A,絕對值排序滿足以下條件：|A[i]| < |A[j]|，只要i < j。例如下面的數組就是絕對值排序：
A:-49, 75, 103, -147, 164,-197,-238,314,348,-422
給定一個整數k，請你從數組中找出兩個元素下標i,j，使得A[i]+A[j] == k。如果不存在這樣的元素配對，你返回(-1,-1)。
對於這個題目，我們曾經討論過當數組元素全是整數時的情況，要找到滿足條件的配對(i,j)，我們讓i從0開始，然後計算m = k - A[i]，接著在(i+1, n)這部分元素中，使用折半查找，看看有沒有元素正好等於m，如果在(i+1,n)中存在下標j，滿足A[j] == m 那麼我們就可以直接返回配對(i,j)，這種做法在數組元素全是正數，全是負數，以及是絕對值排序時都成立，只是在絕對值排序的數組中，進行二分查找時，需要比對的是元素的絕對值。使用這種查找辦法，算法的時間複雜度是O(n*lg(n))。
上面算法形式很緊湊，無論數組全是正數，負數，還是絕對值排序時，都有效。但我們還可以找到效率更高的算法，假設數組中的元素全是同一符號，也就是全是正數，或全是負數時，要找到A[i]+A[j] == k，我們可以這麼做：
1，讓i = 0, j = n-1, 如果A[i] + A[j] == k 那麼算法結束。
2，如果A[i] + A[j] < k, 那麼令 i = i +1;
3，如果A[i] + A[j] > k, 那麼令 j = j -1;
上面步驟一直運行到i == j，或是A[i]+A[j] == k為止。這種做法的時間複雜度是O(n)。其算法效率比前面提到的方法要好，但問題在於，這種做法不能運用於絕對值排序的數組。為了能夠應對絕對值排序的數組，我們需要對算法做一些改進。
對於滿足A[i]+A[j] == k的元素，它必定滿足下面三種情況之一：
1，A[i]和A[j]都是正數。
2，A[i]和A[j]都是負數。
3，A[i]和A[j]是一正一負。
對於前兩種情況我們可以直接使用剛才使用的方法，對於第三種情況，我們需要做一個調整，對於第三種情況，我們讓i指向最後一個整數，讓j指向最後一個負數，如果A[i]+A[j] == k，那麼算法結束，如果A[i]+A[j] > k, 那麼讓i指向下一個正數，如果A[i]+A[j] < k，那麼讓j指向下一個負數。
因此在查找滿足條件的元素配對時，我們先看看前兩種情況是否能查找到滿足條件的元素，如果不行，那麼我們再依據第三種情況去查找，無論是否存在滿足條件的元素配對，我們算法的時間複雜度都是O(n)。我們看看相應的代碼實現：
public class FindPairInAbsoluteSortedArray {
private int[] sortedArray;
private int indexI;
private int indexJ;
private boolean bSuccessed = false;
private int k ;
public FindPairInAbsoluteSortedArray(int[] sortedArray, int k) {
this.sortedArray = sortedArray;
this.indexI = -1;
this.indexJ = -1;
this.k = k;
}
private void findPairWithSameSign(boolean positive) {
/*
* 如果滿足條件的元素對都是正數或負數的話，那麼用i指向第一個正數或負數，j指向最後一個整數或負數，
* 如果兩元素都是正數，如果A[i]+A[j] == k，算法結束，如果A[i] + A[j] > k, 那麼j--；
* 如果A[i]+A[j] < k，那麼i++
*
* 如果兩元素都是負數，A[i] + A[j] == k 算法結束，如果A[i]+A[j]>k, 那麼i++,直到下一個負數
* 如果A[i]+A[j] < k ，那麼j-- 直到下一個負數
*/
int i = 0, j = this.sortedArray.length - 1;
if (positive == true) {
while (this.sortedArray[i] < 0) {
i++;
}
while (this.sortedArray[j] < 0) {
j--;
}
} else {
while (this.sortedArray[i] > 0) {
i++;
}
while (this.sortedArray[j] > 0) {
j--;
}
}
do {
if (this.sortedArray[i] + this.sortedArray[j] == this.k) {
this.bSuccessed = true;
this.indexI = i;
this.indexJ = j;
break;
}
if (this.sortedArray[i] + this.sortedArray[j] < this.k) {
if (positive == true) {
i++;
while (i < this.sortedArray.length && this.sortedArray[i] < 0) {
i++;
}
} else {
j--;
while (j > 0 && this.sortedArray[j] > 0) {
j--;
}
}
}else {
if (positive == true) {
j--;
while (i < this.sortedArray.length && this.sortedArray[j] < 0) {
j--;
}
} else {
i++;
while (i < this.sortedArray.length && this.sortedArray[i] > 0) {
i++;
}
}
}
}while (i < j);
}
private void findPairWithDifferentSign() {
/*
* 把i指向最後一個正數，把j指向最後一個負數，如果A[i] + A[j] == k, 算法結束
* 如果A[i] + A[j] < k，那麼j--;
* 如果A[i] + A[j] > k , 那麼k--
*/
int i = this.sortedArray.length-1;
int j = this.sortedArray.length-1;
while (this.sortedArray[i] < 0 && i > 0) {
i--;
}
while (this.sortedArray[j] > 0 && j > 0) {
j--;
}
do {
if (this.sortedArray[i] + this.sortedArray[j] == this.k) {
this.indexI = i;
this.indexJ = j;
this.bSuccessed = true;
break;
}
if (this.sortedArray[i] + this.sortedArray[j] > k) {
i--;
while (i > 0 && this.sortedArray[i] < 0) {
i--;
}
} else {
j--;
while (j > 0 && this.sortedArray[j] > 0) {
j--;
}
}
}while(i > 0 && j > 0);
}
public void findPair() {
this.findPairWithSameSign(true);
if (this.bSuccessed == false) {
this.findPairWithSameSign(false);
}
if (this.bSuccessed == false) {
this.findPairWithDifferentSign();
}
if (this.bSuccessed == false) {
System.out.println("No such pair exist in array");
} else {
System.out.println("The index are " + this.indexI + " and " + this.indexJ + " with value of " + this.sortedArray[this.indexI] +
" and " + this.sortedArray[this.indexJ]);
}
}
}
類FindPairInAbsoluteSortedArray用於在絕對值排序的數組中查找滿足條件的元素配對，它先根據兩元素都是正數的情況下查找，然後再根據兩元素都是負數的情況下查找，如果這兩種情況都找不到，再嘗試兩元素一正一負的情況下查找，如果三種情況都找不到滿足條件的元素，那麼這樣的元素在數組中不存在。
我們看看入口代碼：
public class Searching {
public static void main(String[] args) {
int[] A = {-49, 75, 103, -147, 164, -197, -238, 314, 348, -422};
int k = 167;
FindPairInAbsoluteSortedArray fi = new FindPairInAbsoluteSortedArray(A, k);
fi.findPair();
}
}
上面代碼運行結果如下：
從運行結果上看，我們算法的實現是正確的，並且這種做法比原先依靠折半查找的效率要高，它的算法複雜度為O(n)，空間複雜度為O(1)。
閱讀更多 wycl16514 的文章
