0169._majority_element.md

169. Majority Element

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/majority-element/description/

内容描述

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]
Output: 2

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

字典记录出现次数，取次数最多对应的key即可

beats 70%

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        lookup = {}
        for num in nums:
            lookup[num] = lookup.get(num, 0) + 1
        max_occur = max(lookup.values())
        for key in lookup:
            if lookup[key] == max_occur:
                return key

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

这个问题有一个很出名的算法

Boyer-Moore众数(majority number) 问题

在数组中找到两个不相同的元素并删除它们，不断重复此过程，直到数组中元素都相同，那么剩下的元素就是主要元素。

这个算法的妙处在于不直接删除数组中的元素，而是利用一个计数变量.

beats 88.66%

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count, candidate = 0, None

        for num in nums:
            if count == 0:
                candidate = num
            count = count + 1 if num == candidate else count - 1
        return candidate