169.Majority Element

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
字数统计: 310 | 阅读时间 ≈ 1

题目描述

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:
Input: [3,2,3]
Output: 3

Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

我的解法

解题思路

按照分治法的标签找到的题目，但是感觉可以直接用一个map来记录每个数字出现的次数，然后再遍历map找到出现最多的次数就可以了。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int i : nums)
            count[i]++;
        int maxNum = 0;
        int maxCount = 0;
        for (auto i : count){
            if (i.second > maxCount){
                maxCount = i.second;
                maxNum = i.first;
            }
        }
        return maxNum;
    }
};

Runtime: 20 ms, faster than 77.92% of C++ online submissions for Majority Element.
Memory Usage: 11.2 MB, less than 48.48% of C++ online submissions for Majority Element.

高票解法

在讨论区看到了一个更加简洁的方法，在统计的同时进行判断，如果大于数组的长度的二分之一就一定是众数了。

实现代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counter;
        for (int num : nums){
            if (++counter[num] > nums.size() / 2)
                return num;
        }
        return 0;
    }
};