Skip to content

Majority Element Problem

Problem Introduction

Given a sequence of \(n\) elements, it is guaranteed that there exists an element \(a\) whose occurrence count strictly exceeds \(n/2\). Find this element.

Approaches

Offline Algorithm

If the entire sequence is known from the beginning, a natural idea is to count the occurrences of each element in the sequence. The element whose occurrence count exceeds \(n/2\) is the majority element. One can create a bucket to count the occurrences of each element and output the element whose count exceeds \(n/2\).

However, the above approach introduces a bucket for counting, which is not optimal in terms of space efficiency. Clearly, if a majority element exists in the sequence, then after sorting, the \(\lfloor n/2\rfloor+1\)-th element of the sequence must be the majority element. Using nth_element, we can find this element. This way, we obtain the majority element with linear time complexity without introducing extra space.

Online Algorithm

In some scenarios, we need to process streaming data online, requiring an algorithm that does not need to know all data in advance but can gradually compute the answer using only the currently given data. The Majority Vote Algorithm 1 is an online algorithm that can solve the majority element problem.

Since the majority element appears more than \(n/2\) times, for a complete sequence, after repeatedly eliminating one majority element and one element different from the majority element, the majority element will eventually remain. Based on this observation, we can design an online algorithm to perform such elimination operations. Let val and cnt be two variables representing the current candidate for the majority element and the number of remaining candidate elements after such elimination operations, respectively. Initially, cnt is set to \(0\). Each time an element is taken from the data stream, if the current cnt is \(0\), it means the majority element candidate has been completely eliminated, and the currently recorded val is definitely not the majority element. Therefore, set the current element as the new candidate. Then, check whether the current element is the candidate. If yes, increase cnt by \(1\); if not, this element should be eliminated together with a candidate, so decrease cnt by \(1\). Repeat the above operations until the data stream is fully read. The final val is the majority element.

Note

When the original data does not contain a majority element, the result given by this algorithm is incorrect. To determine whether a majority element exists in the sequence, it is necessary to read the data stream again, count the occurrences of val, and check whether it exceeds \(n/2\).

To read the data stream again, one can reset the input position indicator using library functions such as std::basic_istream<CharT,Traits>::seekg (for stream input) or rewind, fseek (for C-style input).

Example Problems

Luogu P2397 yyy loves Maths VI (mode)

Find the majority element of the given sequence.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <cstdio>

int main() {
  int n;
  scanf("%d", &n);
  int val, cnt = 0;
  while (n--) {
    int x;
    scanf("%d", &x);
    if (!cnt) val = x;
    (val == x) ? ++cnt : --cnt;
  }
  printf("%d\n", val);
  return 0;
}
LeetCode 229. Majority Element II

Given an integer array of size \(n\), find all elements that appear more than \(\lfloor n/3\rfloor\) times.

Reference Code 
 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
33
34
35
36
37
38
39
class Solution {
 public:
  vector<int> majorityElement(vector<int>& nums) {
    // Extend the majority voting algorithm from "canceling 2 different elements" to "canceling 3 pairwise different elements"
    int maj1, maj2;
    int cnt1 = 0, cnt2 = 0;
    for (int num : nums) {
      if (num == maj1) {
        ++cnt1;
      } else if (num == maj2) {
        ++cnt2;
      } else if (cnt1 == 0) {
        maj1 = num;
        ++cnt1;
      } else if (cnt2 == 0) {
        maj2 = num;
        ++cnt2;
      } else {
        --cnt1;
        --cnt2;
      }
    }

    // Since the problem does not guarantee the existence of 2 elements appearing more than ⌊ n/3 ⌋ times, verification is needed.
    vector<int> ans;
    cnt1 = 0, cnt2 = 0;
    for (int num : nums) {
      if (num == maj1)
        ++cnt1;
      else if (num == maj2)
        ++cnt2;
    }
    int n = nums.size();
    if (cnt1 > n / 3) ans.push_back(maj1);
    if (cnt2 > n / 3) ans.push_back(maj2);

    return ans;
  }
};

References

  1. Majority Vote Algorithm - Wikipedia ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用