[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.

解答：

尋找主元素。主元素有幾個性質：

 

主元素，一定是排序之後序列的中位數；對於一個序列而言，刪除兩個不同的數之和，序列的主元素不變。 排序的話，用快排之後，找中間數。這裡是第二種方法： 但怎麼知道哪個是主元素麼？我們可以假設當前元素是主元素。 這樣，還需要另一個變量來記錄主元素出現次數，當次數為 0 是下一個元素假設為主元素。

class Solution {
public:
    int majorityElement(vector& nums) {
        int count = 0;
        int major = nums[0];
        for(int i = 0; i < nums.size(); i++)
        {
            if(count == 0){
                major = nums[i];
                count++;
            }
            else if(major == nums[i]){
                count++;
            }
            else{
                count--;
            }
        }
        return major;
    }
};