面试算法，在绝对值排序数组中快速查找满足条件的元素配对
面试算法，在绝对值排序数组中快速查找满足条件的元素配对
一个含有多个元素的数组，有多种排序方式。它可以升序排列，可以降序排列，也可以像我们以前章节说过的，以波浪形方式排序，现在我们要看到的一种是绝对值排序。对于数组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++
*/
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) {
i++;
if (positive == true) {
while (i < this.sortedArray.length && this.sortedArray[i] < 0) {
i++;
}
} else {
while (i < this.sortedArray.length && this.sortedArray[i] > 0) {
i++;
}
}
}else {
j--;
if (positive == true) {
while (i < this.sortedArray.length && this.sortedArray[j] < 0) {
j--;
}
} else {
while (i < this.sortedArray.length && this.sortedArray[j] > 0) {
j--;
}
}
}
}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)。