169. Majority Element

169. Majority Element

Easy

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.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]

解: 逐步檢查: 誰一超過一半 就馬上輸出

這樣也滿快的

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        m=len(nums)
        l={}
        for i in nums:
            if i in l:
                l[i]+=1
            else:
                l[i]=1
            if l[i]>m//2:

MOore 投票法:

速度上更快一些 O(n) linear time and O(1) space

class Solution(object):
    
                
    
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count=1
        num=nums[0]
        for i in nums:
            if i==num:
                count+=1
            if i!=num:
                count=count-1
            if count==0:
                num=i
                count=1
        return num
                return i