Majority Element

Given an array of sizen, 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. Hashmap

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

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hashmap = collections.Counter(nums)
        for i in hashmap:
            if hashmap[i] > len(nums)/2:
                return i

2. 排序：将数组排序，因为多数的元素超过一半，因此排序后中间的元素必定是要求的多数元素

O(nlogn)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(nums)[len(nums)/2]

3. Majority Vote Algorithm

“投票算法”，设定两个变量candidate和count。candidate保存当前可能的候选众数，count保存该候选众数的出现次数。

遍历数组num。

如果当前的数字e与候选众数candidate相同，则将计数count + 1

否则，如果当前的候选众数candidate为空，或者count为0，则将候选众数candidate的值置为e，并将计数count置为1。

否则，将计数count - 1

如果存在数字e出现频率超过半数，那么数组中最后剩下的就只有e，最终留下的候选众数candidate即为最终答案。

以上算法时间复杂度为O(n)，空间复杂度为O(1)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candidate, count = None, 0
        for e in nums:
            if count == 0:
                candidate, count = e, 1
            elif e == candidate:
                count += 1
            else:
                count -= 1
        return candidate