这是一道面试题:给定一个整数 x
和一个由 N 个不同整数组成的排序数组 a[]
,设计一个线性时间算法
来确定是否存在两个不同的索引 i 和 j 使得 a[i] + a[j] == x
。不允许辅助存储。
我已经在 Java
中实现了它。但我当前的运行时间是 O(nlogn)
,因为我在每次迭代
上执行了 binarySearch
。所以它不是严格的线性
。我想知道是否存在针对此问题的线性时间解决方案
。如果是这样,关于它的一些指示可能会有所帮助。
谢谢。
public class SumArrayIndex {
public static void main(String[] args){
int[] arr={1,2,3,4,5,6,7,8,9,10};
sumSortedArray(arr, 4);
System.out.println();
sumSortedArray(arr, 19);
System.out.println();
sumSortedArray(arr, 100);
}
public static void sumSortedArray(int[] arr, int sum){
for (int i=0;i<arr.length;i++){
int temp=Arrays.binarySearch(arr, sum-arr[i]);
if (temp>0 && temp!=i){
System.out.printf("The two indices are %s and %s%n ",i,temp);
return;
}
}
System.out.printf("The sum:%s cannot be formed with given array:%s",sum,Arrays.toString(arr));
}
}
最佳答案
您可以根据以下观察将算法修改为线性时间:
- 不失一般性,你可以说
i
和j
是这样的arr[i]<arr[j]
.证明:如果不是这样,你可以交换i
和j
. - 考虑到你一开始就开始搜索,当你搜索
sum-arr[i]
, 您始终可以在索引i
的右侧搜索;如果sum-arr[i] < arr[i]
,你知道没有答案,因为j
会在i
的左边 - 如果您之前搜索过
sum-arr[i]
已在索引k
处结束如果没有结果,您的下一次搜索可以在索引i
之间进行和k
. - 您无需搜索
sum-arr[i]
使用二进制搜索:你可以从后面进行线性搜索,并保持点k
其中arr[k] < sum-arr[i]
作为您的下一个起点。
这让您可以构建一个算法,对每个项目只检查一次。
关于arrays - 找到排序数组的索引,使得 a[i]+a[j]=x,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21687200/