面试经典150题 P169 多数元素

---

时间轴

时间轴

2025-09-29

init

排序

---

题目：

P169 多数元素

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

排序后直接返回中间那个元素就行

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

一个简单事实：如果一个数组有大于一半的数相同，那么任意删去两个不同的数字，新数组还是会有相同的性质。基于这个事实，就引发了类似相消的思想：

由于众数一定占数组大小的一半以上，所以就算其它所有元素都来和它“碰”，到最后还是剩下众数，cur表示目前遍历到的候选众数，count表示目前为止该众数的“净”计数（对于待选众数，遇到相同的就++，遇到不同的就“碰撞”–，如果count变成0，就重新设置候选众数，count从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, 从 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;
        }
};