查找是否有超过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; 
}