如何不斷查找兩個不同列表中的兩個最小值？

我有兩個不同的列表包含整數，我需要不斷找到這兩個列表之間的兩個最小值;我應該注意到，我不想將這兩個列表合併在一起，因爲它們是不同的類型。如何不斷查找兩個不同列表中的兩個最小值？

我想知道我的方法是好還是壞。如果不好，請告訴我如何讓它更有效率。

不斷有由降序排序兩個列表，所以分鐘將在底部
從列表1找到兩個分鐘，並將其與列表2兩分鐘比較，發現兩分鐘出去這四個值的
取下副列表（S）兩分鐘，他們的價值觀結合起來（需要），並把它添加到列表2

我基本上是執行霍夫曼代碼的一部分，我想要以降序排列字符的頻率列表。

來源

2016-05-11 bob dylan

你是什麼意思？這些清單是否隨時間而變化？ – 11thdimension

更新列表之前爲什麼不進行比較？ – shmosel

方法似乎確定...你嘗試過嗎？你有沒有遇到任何性能問題？ – Pras

在List中查找分鐘可以在沒有任何排序的情況下以線性時間完成。每次排序和查找最小值將是O(m*nlgn) m是迭代次數，n是列表大小）。

更好的方法是使用PriorityQueue（min-heap），其中min始終位於堆的頂部，而不是在每次迭代時進行排序。

使用min-heap在實現Huffman codes和一般的貪婪算法中很常見。

來源

2016-05-11 18:58:04

我昨天晚上在想同樣的事情，但我（不知道爲什麼）仍然無法看到實際使用優先級隊列。類似於PQ的想法：找到兩個分鐘，用這兩個分鐘的總和創建一個新值，將其添加到PQ中，然後刪除舊的兩個分鐘/值？ –

@bobdylan準確地說，你可以從兩個隊列中輪詢，得到兩個元素的最小值，並再次推到隊列的最小值 –

@bobdylan小心地調用PriorityQueue池來獲取元素排序不依賴沒有排序的迭代器 –

雖然這肯定會工作，保持隨時排序列表的任務應該是一個值得關注的理由：

如果你的列表允許隨機存取（即ArrayList S），那麼刪除的過程從他們身上花費你爲O（n）
如果你的列表允許O（1）缺失（即LinkedList S），然後找到插入點的過程是O（n）

也就是說之上最初的排序，這會花費你O（n * 1 og n）。換句話說，首先排序你的列表沒有任何好處：維護它們會花費你每次操作的O（n），所以你不妨做線性搜索。

換句話說，該算法的工作原理，但效率低下。不使用維護排序列表，而是使用保持最小或最大值的容器，並允許快速插入/刪除（例如PriorityQueue）。

來源

2016-05-11 19:00:42 dasblinkenlight

爲什麼不把你的最小值保存在變量中，而不是保留排序列表？

List<Integer> list1, list2; 
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE; 

void setMin(int newValue) { 
    if (newValue < min1) { 
     min1 = newValue; 
    } else if (newValue < min2) { 
     min2 = newValue; 
    } 
} 

void updateList1(int newValue) { 
    setMin(newValue); 
    list1.add(newValue); 
} 

void updateList2(int newValue) { 
    setMin(newValue); 
    list2.add(newValue); 
}

來源

2016-05-11 19:38:51 shmosel

當你從列表中刪除一個元素時會發生什麼？ –

@SleimanJneidi，OP沒有提到這種可能性。但我想這會取消該解決方案的資格。 – shmosel

如何不斷查找兩個不同列表中的兩個最小值？

回答

相關問題