如何查找n項列表中的任何項目是否被重複超過n/2次。我希望它很快,所以它應該是O(nlogn),這裏是踢球者:你只能檢查項目是否相等,沒有別的。即時有一個很難做的比Ø更好的(N^2)查找是否有超過n/2個項目在n個項目列表中匹配。 O(nlog(n))
-3
A
回答
0
如果你只能檢查平等那麼這裏是一個O(nlogn)
解決方案:
- 排序列表中
O(nlogn)
時間 - 設中間元素爲排序後的數組中的
m
- 現在,如果有一個重複超過
n/2
次的元素,它只能是m
。所以現在可以通過迭代到中間索引的右側和中間索引的左側來檢查m
的頻率。如果它超過n/2
你找到了答案,否則該元素不存在。
如果您可以做的不僅僅是檢查相等性,還可以通過數組並將元素的頻率存儲在HashMap中,然後檢查頻率是否大於n/2
。該解決方案的時間複雜度爲O(n)
。
代碼O(n)
溶液HashMap中:
public int getDuplicated(List<Integer> a) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int n = a.size();
for (int i = 0; i < a.size(); i++) {
if (map.containsKey(a.get(i))) {
// increasing the frequency
map.put(a.get(i), map.get(a.get(i)) + 1);
} else {
map.put(a.get(i), 1);
}
if (map.get(a.get(i)) > n/2) {
// element found
return a.get(i);
}
}
// returning -1 if could not find the element
return -1;
}
+0
除非可以進行排序比較,否則無法排序;平等比較是不夠的。另一方面,哈希映射不需要有序比較,但它確實需要能夠操縱項目而不僅僅是比較。 – rici
相關問題
- 1. TCL獲取每個列表中匹配列表中的第n個項目
- 2. 查找列表中第n個項目的索引
- 3. 如何有效地找出一個序列是否至少有n個項目?
- 4. MS SQL,查看一個列表中的任何項目是否與另一個列表中的項目匹配
- 5. 什麼是一種有效的方式,以匹配n個項目對應n個項
- 6. 查找是否有在出現的陣列的數目超過N/8倍
- 7. O(nlog * n)和O(n)之間?
- 8. 正則表達式 - 如何匹配列表中的至少n個項目
- 9. Linq匹配查找列中的項目與多個條目
- 10. 從IList中刪除匹配謂詞中的N個項目
- 11. 排序項n個條目
- 12. 是否可以創建一個引用n個現有項目和一個新項目的多項目模板?
- 13. 子設置行是列表中匹配項的+ - N項
- 14. 項目在陣列中出現超過n/2次A
- 15. 查找多個列表中的匹配項,並根據4個項目中的3個組合匹配
- 16. 找到最後一個項目,但沒有儲存n個項目的流中的N爲
- 17. 找到固定項目重複列表中的第n項
- 18. 從列表中有條件地刪除N個項目
- 19. 查找與標準匹配的第一個序列項目
- 20. O(N)查找,但O(日誌(N))的比較排序列表
- 21. 在N組中找到N個項目的所有組合,而不用重複項目組合(python)?
- 22. 編輯列表中每個第N個項目的值
- 23. sed:是否有一個選項可以替換每行匹配的第N個和第M個匹配項?
- 24. 防止Django用戶創建超過N個項目
- 25. 蟒蛇循環在列表中的n個連續項目
- 26. 每n個項目在收集在VB.Net
- 27. 知道一個Python列表是否有一個項目或多個項目
- 28. PostgreSQL的:每個項目的前N個項目在同一個表
- 29. 查找多個列表中的項目?
- 30. 代碼O(nlog(n))的T(n)如何?
使用[博耶-摩爾多數票算法(https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm),如描述在對建議重複的各種答案中。算法是O(n),超出您的規格。如果您不知道最常見的元素是多數元素,則需要進行第二次掃描以計算boyer-moore算法找到的元素的出現次數。 – rici