Cover image for Interview Classic 150 Questions P169 Majority Element

Interview Classic 150 Questions P169 Majority Element

(Updated: )
algorithm
, ,
Timeline

Timeline

2025-09-29

init

Sorting

Title:

P169 Majority Element

https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

After sorting, just return the middle element.

1
2
3
4
5
6
7
8
9
10
11
12
#include <algorithm>
#include <vector>

using std::vector;

class Solution {
public:
  int majorityElement(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
  }
};

A simple fact: If an array has more than half of its numbers the same, then deleting any two different numbers will still leave the new array with the same property. Based on this fact, a similar elimination idea arises:

Since the majority element must occupy more than half of the array size, even if all other elements come to ‘collide’ with it, in the end the majority element remains. cur represents the current candidate majority element, count represents the ‘net’ count of that majority element so far (for the candidate majority, increment on same, decrement on different, if count becomes 0, reset candidate majority and set count to 1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int i, n = nums.size();

        int candidate = nums[0];
        int cnt = 1;

        for(i = 1 ; i < n; i++){
            if(candidate == nums[i]){
                cnt ++;
            }else{
                cnt --;
                if(cnt == 0){
                    candidate = nums[i];
                    cnt = 1;
                }
            }
        }
        return candidate;

    }
};

LeetCode Hot 100 rewrite, starting from 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
using std::vector;

class Solution {
    public:
        int majorityElement(vector<int> &nums)
        {
                int i, n = nums.size();
                int target = nums[0], cnt = 0;

                for (i = 0; i < n; i++) {
                        if (nums[i] == target) {
                                cnt++;
                        } else {
                                cnt--;
                                if (cnt == 0 && i != n - 1)
                                        target = nums[i + 1];
                        }
                }

                return target;
        }
};