給定多個排序陣列，從所有陣列中收集 K 個最大值的最有效方法是什么？
例如：
輸入：
K = 5
陣列1：[100、50、30、20、10]
array2: [400, 50, 20, 0]
array3: [0, 0, 0, 0]
輸出：
[400、100、50、50、30]
謝謝。
uj5u.com熱心網友回復：
這是一個O(N (K * log N))解決方案，其中 N 是陣列的數量。
首先，通過取 N 個陣列中每個陣列的最高元素來創建一個最大堆，這可以及時完成O(N)。
然后，對于 K 次迭代：從堆的頂部彈出 inO(log N)并插入對應陣列的元素，該元素位于剛剛彈出的陣列之后O(log N)。
回圈確實O(log N)有效，因此復雜性是O(N (K * log N))
uj5u.com熱心網友回復：
將所有陣列放入優先級佇列（因此??在示例中，優先級佇列將具有三個值），由這些陣列中的第一個值作為鍵。對優先級佇列使用有效的實作，例如二進制堆。
當您從佇列中彈出一個專案時，從相應的陣列*中提取第一個值，如果該陣列還不是空的，則將其再次插入優先級佇列，現在由其當前的第一個元素作為鍵。
執行此K次以獲得前K個值。
*為了避免非常量的時間復雜度，您可以在陣列上維護一個迭代器（如遞增的索引......），而不是真正從陣列中提取該值。
uj5u.com熱心網友回復：
這些型別的問題使用優先級佇列來解決。在每一步，我們都需要從所有陣列的最大元素中找出最大元素。優先級是關鍵。我們將所有陣列的最頂層元素與相應陣列的參考一起放入優先級佇列中。比較器將只使用該值并且存在參考，因此當我們彈出一個元素時，我們可以將該陣列的下一個元素放入優先級佇列中。
附上一個非常相似的問題的鏈接，以便您可以與我的解決方案一起練習。 https://leetcode.com/problems/merge-k-sorted-lists/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
if(k==0){
return null;
}
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(k, (x,y)->x.val-y.val);
for(ListNode list: lists){
if(list != null)
q.add(list);
}
ListNode ans = new ListNode();
ListNode temp = ans;
while(!q.isEmpty()){
ListNode curr = q.poll();
temp.next = curr;
temp = temp.next;
if(curr.next != null){
q.add(curr.next);
}
}
return ans.next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/488631.html
上一篇：從陣列C 中洗掉重復項
下一篇：帶前綴的字串匹配