Leetcode 169.多数元素【C++】

本文最后更新于:2020年11月19日 上午

地址:https://leetcode-cn.com/problems/majority-element

题目

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

解题思路

思路很简单,就是遍历数组记录每一个元素的个数,由于最终是要返回元素,所以需要将元素和其个数成对保存,我使用了 vector<pair<int, int>> 的数组来存储。

遍历数组,先到 aNums[] 中查找 num 是否已存在,如果已存在则将其个数+1;不存在,则将其添加到 aNums[] 并将其个数初始化为1。

题目已经说明“给定的数组总是存在多数元素”,所以可以确定出现次数大于 ⌊ n/2 ⌋ 的多数元素有且仅有一个。所以每遍历一个元素,我们就判断其个数是否大于 nums.size() / 2 ,一旦有一个元素的个数大于 nums.size() / 2 则说明这个元素就是要求的多数元素,直接将该元素返回即可。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //可作为跳出循环的条件,因为多数元素只存在一个
        int low = nums.size() / 2;
        vector<pair<int, int>> aNums;//保存元素及其个数
        //统计不同元素的个数,一旦某个元素的个数大于low则可直接返回这个元素
        for (auto num : nums) {
            int quantity = 0;//num的个数
            //查找aNums[]中是否已有num的记录
            for (int i = 0; i < aNums.size(); i++) {
                //如果有的话,将其数量+1,并更新quantity
                if (aNums[i].first == num) {
                    aNums[i].second++;
                    quantity = aNums[i].second;
                    break;
                }
            }
            //quantity==0表明num第一次遇到
            if (quantity == 0) {
                aNums.push_back({ num,1 });//将其添加到aNums[]中,数量初始化为1
                quantity = 1;//更新num的数量为1
            }
            if (quantity > low)
                return num;
        }
        return 0;//遍历完整个数组之前一定能返回结果,不会运行到这一步
    }
};