Majority

题目描述

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.

解题方法

Brute Force

Always先尝试用最直接的方法解决。这一题最直接的方法就是用一个hashtable记录下每个number出现的 次数，然后再找出出现次数大于n/2的数。

时间复杂度: O(n) 空间复杂度: O(n)

Moore's voting Algorithm

利用Moore's voting algorithm可以在空间O(1)的情况下找到。

基本思路就是keep一个variable x,

  • 如果等于x， count就加1
  • 当count为0时，就将x设为当前的值
  • 用所有不等于x的element将count减1
  • 那么到最后剩下来的那个就是Majority number.
  • 得到这个Number后再计算一遍它的出现次数来验证
    • (不要忘了，特别是在不保证有majority number的情况下)

Solution

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

        countX = 0
        for num in nums:
            if num == x:
                countX += 1

        if countX > length / 2:
            return x
        else:
            return

Reference