首页 > 其他 > 详细

[LeetCode]Majority Element

时间:2015-02-07 14:34:21      阅读:256      评论:0      收藏:0      [点我收藏+]

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.

这道题是计算出一组数中出现频率大于? n/2 ?次的那个数。我的思路简单粗暴,使用STL中的map,键为数组中的元素,值为元素对应的频率。遍历一边数组,计算各自的频率,最后选出map中值大于? n/2 ?对应的键。

贴上代码:

class Solution {
public:
    int majorityElement(vector<int> &num) {
        map<int, int> m;
        for (int i = 0; i < num.size(); i++){
            m[num[i]]++;
        }
        map<int, int>::iterator it = m.begin();
        int count = num.size() / 2;
        for (; it != m.end(); it++){
            if (it->second >= count)
                return it->first;
        }
    }
};

当然了,简单粗暴的结果就是74ms…QAQ
算了,不高兴优化了【看到有人一行Python就解决了 o(>﹏<)o】

[LeetCode]Majority Element

原文:http://blog.csdn.net/kaitankedemao/article/details/43602845

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!