Find the top k sums of two sorted arrays
That can be easily done in
O(k)
. I'll only assume arrays are sorted in descending order, to simplify notation. The idea is simple. We'll find 1st, 2nd, .., k-th maximum values one by one. But to even consider pair
(i, j)
we need to have both (i-1, j)
and (i, j-1)
already selected, because they both are greater or equal than (i, j)
. It's much like if we push all
n*m
pairs into the heap and then remove max k
times. Only we don't need all n*m
pairs. heap.add(pair(0, 0)); // biggest pair
// remove max k-1 times
for (int i = 0; i < k - 1; ++i) {
// get max and remove it from the heap
max = heap.popMax();
// add next candidates
heap.add(pair(max.i + 1, max.j));
heap.add(pair(max.i, max.j + 1));
}
// get k-th maximum element
max = heap.popMax();
maxVal = a[max.i] + b[max.j];
Some things to consider.
Duplicated pairs can be added to the heap, this can be prevented with hash.
Indexes need to be validated, e.g. that
max.i + 1 < a.length
. _______________________________________________________________________
This can be done in O(klogk) using a max-heap.
1.Start from the first two elements of the sorted arrays.Store their sum and the corresponding index into from the arrays in the heap i.e first element of the heap will contain (A[0]+B[0], 0-->index in array A,0-->index in array B)
2.We need to do Extract_Max operation k times and we need to insert two elements at each step.So there'll be at max 2*k insertions and each step we'll insert two elements based on the element extracted. Suppose for the node extracted...i--->index in array A and j--->index in array B. Then we'll insert A[i + 1][j] and A[i][j + 1] in the heap.
So the complexity will be O(klogk).
sorry we need to insert (A[i] + B[j+1],i,j+1) and (A[i+1]+B[j],i+1,j) instead of A[i][j+1] and A[i+1][j].
여기에 max heap를 실현하는 코드가 있습니다.http://blog.csdn.net/jiyanfeng1/article/details/41404243
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
convert a sorted array into a balanced binary search treeGiven a sorted array, and converted it into a balanced binary search tree. Solution: If you would have to choose an arra...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.