项目在阵列中出现超过n/2次A

Question

数组A[1 : : : n]由项目填充形成一些无限集合S.（S不需要是一组 数字，并且不需要定义它的顺序关系。 ）描述最坏情况时间复杂度为O（n）的算法，以确定某个项目在阵列A中是否出现超过 n/2次。不要忘记争辩说，您的算法是正确的，并且T（ n） 确实是O（n）。

Answer 1

这是一个两步过程。

1. 获取大部分时间在数组中出现的元素。这个阶段将确保如果有多数元素，那么它只会返回。
2. 检查从上述步骤获得的元素是否是多数元素。

伪代码：

findCandidate(a[], size) 
1. Initialize index and count of majority element 
    maj_index = 0, count = 1 
2. Loop for i = 1 to size – 1 
    (a) If a[maj_index] == a[i] 
      count++ 
    (b) Else 
     count--; 
    (c) If count == 0 
      maj_index = i; 
      count = 1 
3. Return a[maj_index] 

检查如果在步骤1中获得的元素是大多数

printMajority (a[], size) 
1. Find the candidate for majority 
2. If candidate is majority. i.e., appears more than n/2 times. 
     Print the candidate 
3. Else 
     Print "NONE" 

reference