169. Majority Element

发表于 | 分类于 ， | 阅读次数:

Total Accepted: 92197
Total Submissions: 232301
Difficulty: Easy

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.

还是hash，hash中过半即答案

C++:

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

打个小广告

欢迎加入我的小专栏「基你太美」一起学习。