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

# Majority Element

## 169. Majority Element

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.

#### Boyer-Moore Voting Algorithm

利用一個count 計算candidate and non-candidate 出現次數。當為0時切換candidate. Array的 pre candidate count不重要, suffix candidate is sufficient

```
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7] => 7
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5] => 5
```

[Source](https://leetcode.com/problems/majority-element/solution/)

```python
def majorityElement(self, nums: List[int]) -> int:
    count = 0
    cand = None
    
    for n in nums:
        if count == 0:
            cand = n
        count += 1 if cand == n else -1
        
    return cand
```

## 229. Majority Element II

Given an integer array of size n, find all elements that appear more than `⌊ n/3 ⌋` times.

**Note:** The algorithm should run in linear time and in O(1) space.

```python
"""
if condition先後次序重要, 先判斷cand1, cand2 exist
"""
def majorityElement(self, nums: List[int]) -> List[int]:
    cand1, cand2 = None, None
    count1, count2 = 0, 0
    
    for n in nums:
        if n == cand1:
            count1 += 1
        elif n == cand2:
            count2 += 1
        elif count1 == 0:
            cand1 = n
            count1 = 1
        elif count2 == 0:
            cand2 = n
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1
            
    return [x for x in (cand1, cand2) if nums.count(x) > len(nums) // 3]
```