问题: 给定一个无序的正整数数组,是否可能从该数组中找到一对整数,使它们的和等于给定的总和?
约束条件: 该算法应该在O(n)的时间复杂度内原地完成(不使用任何外部存储器,如数组、哈希映射等) (您可以使用额外的变量/指针)
如果这不可能,是否可以给出证明?
问题: 给定一个无序的正整数数组,是否可能从该数组中找到一对整数,使它们的和等于给定的总和?
约束条件: 该算法应该在O(n)的时间复杂度内原地完成(不使用任何外部存储器,如数组、哈希映射等) (您可以使用额外的变量/指针)
如果这不可能,是否可以给出证明?
如果你有一个已排序的数组,你可以通过将两个指针向中间移动,在O(n)时间内找到这样一对元素。
i = 0
j = n-1
while(i < j){
if (a[i] + a[j] == target) return (i, j);
else if (a[i] + a[j] < target) i += 1;
else if (a[i] + a[j] > target) j -= 1;
}
return NOT_FOUND;
如果你对数字的大小有限制(或者数组一开始就是有序的),那么排序可以做到O(N)。即使如此,log n因子很小,我不想费心去刨掉它。一个在已排序数组上的时间复杂度为O(N)
,空间复杂度为O(1)
的解决方案:
设M
是你想要的值。使用两个指针X
和Y
。将X=0
置于开头,将Y=N-1
置于末尾。计算和sum = array[X] + array[Y]
。如果sum>M
,则将Y
减少;否则将X
增加。如果这两个指针相交,则没有解。
你可以原地排序来处理一般数组,但我不确定是否有一般情况下时间复杂度为O(N)
、空间复杂度为O(1)
的解决方案。
以下是我的Java解决方案(时间复杂度为O(n)),它将输出所有给定和的配对
import java.util.HashMap;
import java.util.Map;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<Integer, Integer> hash = new HashMap<>();
int arr[] = {1,4,2,6,3,8,2,9};
int sum = 5;
for (int i = 0; i < arr.length; i++) {
hash.put(arr[i],i);
}
for (int i = 0; i < arr.length; i++) {
if(hash.containsKey(sum-arr[i])){
//System.out.println(i+ " " + hash.get(sum-arr[i]));
System.out.println(arr[i]+ " " + (sum-arr[i]));
}
}
}
}
正如 @PengOne 所提到的,通常情况下是不可能的。但是如果对输入数据做一些限制。
第1步:将所有小于SUM的元素移动到数组的开头,在N次操作中,我们将数组划分为[0,K]和[K,N-1],使得[0,K]包含元素<= SUM。
第2步:由于我们知道范围(0到SUM),因此我们可以使用基数排序。
第3步:在A[K]上使用二分查找,好处之一是,如果我们需要查找补充元素,则仅需要查看A[K]的一半。因此,在A[k]中,我们迭代 A [0 to K / 2 + 1],需要在A[i to K]中进行二进制搜索。
因此,总时间约为 N + K + K/2 lg (K),其中 K 是输入 A[N] 中 0 到 Sum 之间的元素数量。
注意:如果您使用 @PengOne 的方法,则可以在K步骤中完成步骤3。因此,总时间将为 N+2K,这绝对是 O(N)。
我们不使用任何额外的内存,但会破坏输入数组,但由于开始时它没有任何排序,因此这也不是什么问题。
如果数组中包含数字,且你事先知道其上限,则可以使用计数排序或基数排序(O(n))并使用@PengOne建议的算法来实现。
否则,我想不出O(n)解决方案。但是,O(nlgn)解决方案可以这样实现:
首先使用归并排序或快速排序(用于原地排序)对数组进行排序。查找是否在排序后的数组中存在sum - array_element。 可以使用二分搜索进行查找。
So total time complexity: O(nlgn) + O(lgn) -> O(nlgn).
var arr = [-4, -3, 3, 4];
var lengtharr = arr.length;
var i = 0;
var j = 1;
var k = 1;
do {
do {
if (arr[i] + arr[j] === 0) { document.write(' Elements arr [' + i + '] [' + j + '] sum 0'); } else { document.write('____'); }
j++;
} while (j < lengtharr);
k++;
j = k;
i++;
} while (i < (lengtharr-1));
take two pointers one starts from 0th index of array, and another from end of array say (n-1).
run the loop until low <= high
Sum = arr[low] + arr[high]
if(sum == target)
print low, high
if(sum < target)
low++
if(sum > target)
high--
Step 2 to 10 takes O(n) time, and counting sort takes O(n). So total time complexity will be O(n).
n
个可以读取内存的处理器的情况下,生成n
个线程以在O(n)
时间内进行搜索是否不可行? :) - corsiKa