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)。

一種高效的方法只需遍歷一次數組即可。我們知道主元素出現的次數比其他元素出現的次數和還要大，因此，只需使用兩個變量：candidate和 count這兩個變量記錄了元素candidate的值，count記錄了元素candidate比其他元素多出現的次數。

遍歷數組，遇到與當前記錄元素candidate相同的元素值，++count；否則count被抵消一次，--count。當count變為0時，更換candidate為當前遍歷所在的像素值。

由於遍歷完數組後，主元素被抵消的次數count比然大於零，不會因為當count變為0而被其他數組元素替代，因此candidate也只會是主元素。

三. 示例代碼

class Solution {
public:
    int majorityElement(vector& 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;
    }
};