항목이 배열 n/2 번 이상 나타납니다

Question

배열 은 무한 집합 S를 구성하는 항목으로 채워집니다 (S는 숫자 집합이 아니어야하며 순서 관계를 지정할 필요가 없습니다).) 어떤 항목이 배열 A에서 n/2 번 이상 나타나는지 확인하기 위해 O (n) 인 최악의 경우의 시간 복잡도 인 으로 알고리즘을 설명하십시오. 알고리즘이 정확하고 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