`
十戒和尚
  • 浏览: 4097 次
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

OJ 169 Majority Element

 
阅读更多

题目要求: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.
我的解法:

int majorityElement(vector<int> &num) {
    int key = num.back();
    int k = num.size();
    k--;
    int i = k-1;
    while (i >= k/2)
    {
        if (num[i] != key)
        {
            num[i] = num[k-1];
            k--;
            key = num[k-1];
            k--;
            i=k-1;
            continue;
        }
        i--;
    }
    return key;
}

分析:首先要知道一个定理,如果一个序列中存在一个出现率大于1/2的元素,我们记为mE,那么如果去掉这个序列中的两个不相同的元素,新序列中一定存在一个出现率大于1/2的元素,依然是mE。
该算法最差情况需要在i指向第一个元素的时候,也就是算法的复杂度最差是O(n),最好的情况需要n/2。

这个问题还可以直接考虑,通过map来计数,来获取所求的元素。代码如下:

int majorityElement(vector<int> &num) {
    map<int, int> count;
    for (int i : num)
    {
        if (++count[i] >= num.size() / 2)
        {
            return i;
        }
    }
}
<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics