【LeetCode】169. Majority Element

LeetCode-169

Links:https://leetcode.com/problems/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.

思路：

1.Moore’s Voting Algorithm，由Robert S.Boyer 和J Strother Moore于1980年发明，是线性时间复杂度。

2.Hash计数

3.sort

这里给出第一种方法：

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

class Solution {

public:

int majorityElement(vector<int>& nums) {

int count=0,majority;

for(int i=0;i<nums.size();i++)

{

if(count == 0)

count +=1,majority = nums[i];

else

majority == nums[i]?count ++:count --;

}

return majority;

}

};

【LeetCode】169. Majority Element

Tagged on: LeetCode