Как найти kth наибольшее число в попарных суммах как ость + setB?
Я только использовал JProfiler (и некоторый JProbe). Насколько я могу сказать, одно ограничение YourKit - то, что они, кажется, не поддерживают JDK 1.4.2. Это не проблема для многих людей, но это могло бы быть.
3 ответа
If k is very close to 1 or N, any algorithm that generates the sorted sums lazily could simply be run until the kth or N-kth item pops out.
In particular, I'm thinking of best-first search of the following space: (a,b) means the ath item from A, the first list, added to the bth from B, the second.
Keep in a best=lowest priority queue pairs (a,b) with cost(a,b) = A[a]+B[b].
Start with just (1,1) in the priority queue, which is the minimum.
Repeat until k items popped:
pop the top (a,b)
if a<|A|, push (a+1,b)
if a=1 and b<|B|, push (a,b+1)
This gives you a saw-tooth comb connectivity and saves you from having to mark each (a,b) visited in an array. Note that cost(a+1,b)>=cost(a,b) and cost(a,b+1)>=cost(a,b) because A and B are sorted.
Here's a picture of a comb to show the successor generation rule above (you start in the upper left corner; a is the horizontal direction):
|-------
|-------
|-------
It's just best-first exploration of (up to) all |A|*|B| tuples and their sums.
Note that the most possible items pushed before popping k is 2*k, because each item has either 1 or 2 successors. Here's a possible queue state, where items pushed into the queue are marked *:
|--*----
|-*-----
*-------
Everything above and to the left of the * frontier has already been popped.
For the N-k
See also: sorted list of pairwise sums on SO, or the Open problems project.
Сортировка массивов A и B: O (mlogm + nlogn) Примените модифицированную форму алгоритма для объединения 2 отсортированных массивов: O (m + n) т.е. в каждой точке u суммирует два элемента. Когда у u есть (m + n-k + 1) -й элемент в C, прекратите объединение. Этот элемент по существу k-й по величине. Например {1,2} & {3,4}: отсортировано C: {1 + 3, (1 + 4) | (2 + 3), 2 + 4}
Ну, O (n) было бы нижней границей (хотя, вероятно, не жестко), иначе вы могли бы запустить алгоритм O (n) n раз, чтобы получить отсортированный список за O (n ^ 2).
Можете ли вы предположить, что два набора отсортированы (вы представляете их в отсортированном порядке выше)? Если это так, вы могли бы получить что-то со средним кейсом, что прилично лучше, выполнив «ранний выход», начиная с последней пары элементов и т. Д. Но только догадка.