首页 > 代码库 > leetcode笔记:Majority Element

leetcode笔记: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.

二. 题目分析

题目说到,给定一个数组。内含n个元素。找出一个主元素,该元素在数组中出现的次数比其它元素出现的次数加起来还要多。即该元素的数量大于n/2

開始的思路,自然是对数组进行排序,数组最中间的元素就是主元素,但算法复杂度一般须要:O(nlogn);若同意辅助内存。可新建一个数组。用于存放不同元素值在数组中存放的次数。这样仅仅需遍历一次原数组,然后再遍历一次记录次数的数组就可找出主元素。算法复杂度为O(n)

一种高效的方法仅仅需遍历一次数组就可以。

我们知道主元素出现的次数比其它元素出现的次数和还要大,因此,仅仅需使用两个变量:candidatecount这两个变量记录了元素candidate的值,count记录了元素candidate比其它元素多出现的次数。

遍历数组,遇到与当前记录元素candidate同样的元素值,++count;否则count被抵消一次。--count。当count变为0时,更换candidate为当前遍历所在的像素值。

由于遍历完数组后,主元素被抵消的次数count比然大于零,不会由于当count变为0而被其它数组元素替代。因此candidate也仅仅会是主元素。

三. 演示样例代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0, count = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (count == 0)
            {
                candidate = nums[i];
                ++count;
            }
            else
            {
                if (candidate == nums[i])
                    ++count;
                else
                    --count;
            }
        }
        return candidate;
    }
};
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

leetcode笔记:Majority Element