> For the complete documentation index, see [llms.txt](https://rachel2011.gitbook.io/leetcode_cc150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://rachel2011.gitbook.io/leetcode_cc150/leetcode/majority-element.md).

# 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
```