寻找数列主元素

Problem link

Finding a integer that appears at least (N+1)/2 times in the array.

摩尔投票法

The Boyer-Moore Voting Algorithm (Moore’s Voting Algorithm) is a highly efficient method to find the majority element in a sequence (an element that appears more than half the time). It operates in O(n) time and uses O(1) space.

Key Idea:

The algorithm works by maintaining a candidate for the majority element and a counter to track its occurrences. It leverages a “pairing” or “cancellation” mechanism to eliminate non-majority elements.

Steps:

  1. Initialize:
    • Set the candidate to None and the count to 0.
  2. First Pass (Finding the Candidate):
    • Traverse the array:
      • If count == 0, set the current element as the candidate and set count = 1.
      • If the current element matches the candidate, increment count.
      • If the current element differs from the candidate, decrement count.
  3. Second Pass (Validation):
    • After completing the first pass, the candidate is the potential majority element. To confirm, traverse the array again and count the occurrences of the candidate. If it appears more than half the time, it is the majority element; otherwise, there is no majority element.

Time and Space Complexity:

  • Time Complexity: O(n) – two passes through the array.
  • Space Complexity: O(1) – constant space is used for the candidate and count.

Key Reasons for its Effectiveness:

1. Majority Element Dominates:

If there is a majority element, it must appear more than half the time in the array. Let’s say the majority element is M, and the number of occurrences of M is greater than half of the total elements in the array (i.e., count(M) > n/2).

In any process of matching pairs of elements, M will never be fully canceled out because it occurs more frequently than any other element.

2. Cancellation Process:

During the first pass, the algorithm essentially “cancels out” elements that are different from each other by using the count to increase and decrease based on whether an element matches the current candidate.

  • Every time an element that is not the candidate is encountered, the count is decreased, effectively canceling out both the current candidate and the opposing element.
  • When the count reaches zero, a new candidate is chosen. This new candidate can still be the majority element or a temporary placeholder if more occurrences of the majority element appear later.

This step ensures that elements that appear fewer times will eventually be canceled out by the majority element.

3. Why the Majority Element Survives:

The majority element will not be canceled out completely because it appears more than half the time. Even though other elements may reduce the count temporarily, the majority element’s higher frequency ensures that it will eventually remain as the candidate by the end of the first pass.

Example Walkthrough:

Consider an array [2, 2, 1, 1, 1, 2, 2]:

  1. Initial candidate = None, count = 0.
  2. First element 2: count == 0, so candidate = 2, count = 1.
  3. Second element 2: candidate == 2, count = 2.
  4. Third element 1: candidate != 1, count = 1.
  5. Fourth element 1: candidate != 1, count = 0.
  6. Fifth element 1: count == 0, so candidate = 1, count = 1.
  7. Sixth element 2: candidate != 2, count = 0.
  8. Seventh element 2: count == 0, so candidate = 2, count = 1.

After this, candidate = 2. In the verification step, 2 appears 4 times, which is more than n/2 = 3.5, confirming it is the majority element.

Code

This problem guarantees that there will be an answer. So we don’t need the step of check.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<string>
#include<algorithm>
#include<iomanip>
#define ll long long
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        ll ans = 0;
        ll cnt = 0;
        ll x;
        for(int i=1;i<=n;i++){
            scanf("%lld",&x);
            if(cnt==0){
                ans = x;
                cnt = 1;
            }else{
                if(ans==x){
                    cnt++;
                }else{
                    cnt--;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}