項目在陣列中出現超過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