Top Interview 150 P169 Majority Element

---

Timeline

Timeline

2025-09-29

init

Sort

---

Problem:

P169 Majority Element

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

Just sort and return the middle element.

#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 more than half of the numbers in an array are the same, then after arbitrarily deleting two different numbers, the new array still has the same property. This fact leads to a cancellation-like idea:

Since the majority element always occupies more than half of the array, even if all other elements come to ‘collide’ with it, the majority element will still remain in the end. cur represents the candidate majority element currently traversed, and count represents the ‘net’ count of this candidate so far. (For the candidate majority, increment when encountering the same value, ‘collide’ and decrement when encountering a different value; if count becomes 0, reset the candidate majority and set count to 1.)

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

#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;
        }
};