查找是否有超過n/2個項目在n個項目列表中匹配。 O（nlog（n））

Question

如何查找n項列表中的任何項目是否被重複超過n/2次。我希望它很快，所以它應該是O（nlogn），這裏是踢球者：你只能檢查項目是否相等，沒有別的。即時有一個很難做的比Ø更好的（N^2）

Answer 1

如果你只能檢查平等那麼這裏是一個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; 
}