多数元素

## 1 题目

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

**示例 1：**

```txt
输入：[3,2,3]
输出：3
```

**示例 2：**

```txt
输入：[2,2,1,1,1,2,2]
输出：2
```

**进阶：**

* 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

## 2 解题思路

### 2.1 计数

#### 2.1.1 问题分析

1. 最原始的思路是**通过一个 $map$**，其中 $key$**为数组中的元素**，$value$**为对应元素出现的次数**，**添加完元素后**，**如果当前元素的出现次数大于 $\frac{n}{2}$**，则**该元素即为多数元素**，**直接返回即可**。

#### 2.1.2 参考代码

```java
/**
 * 169. 多数元素（版本 1：计数）
 * @param nums  数组
 * @return  数组中出现次数 大于 ⌊ n/2 ⌋ 的元素
 */
public int majorityElementV1(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int m = nums.length;

if (m == 1) {return nums[0];}

for (int i = 0; i < m; i++) {
        int key = nums[i];
        if (!map.containsKey(key)) {
            map.put(key, 1);
        } else {
            int value = map.get(key);
            value++;
            if (value > m / 2) {
                return key;
            } else {
                map.put(key, value);
            }
        }
    }

return -1;
}
```

### 2.2 排序

#### 2.2.1 问题分析

1. 对数组中的元素进行**升序排序**，因为**多数元素的个数大于 $\frac{n}{2}$**，因此**排序后数组的中间位置的元素即为多数元素**。

#### 2.2.2 参考代码

```java
/**
 * 169. 多数元素（版本 2：排序）
 * @param nums  数组
 * @return  数组中出现次数 大于 ⌊ n/2 ⌋ 的元素
 */
public int majorityElementV2(int[] nums) {
    Arrays.sort(nums);
    //  因为多数元素在数组中出现的次数大于 n / 2，因此位于中间位置的元素一定是中位数
    return nums[nums.length >> 1];
}
```

### 2.3 摩尔排序

#### 2.3.1 问题分析

1. **开始时将投票人 $voteItem$ 初始化为 0**，**票数 $voteNum$ 初始化为 0**，然后**对数组 $nums$ 进行遍历**，假设当前遍历到的元素 $nums[i]$ 为
   1. 如果 $voteNum = 0$：则令 $voteItem = nums[i], voteNum = 1$。
   2. 如果 $voteItem != nums[i]$，则 $voteNum = voteNum - 1$。
   3. 如果 $voteItem = nums[i]$，则 $voteNum = voteNum + 1$。
2. 这种方法之所以行得通是因为**投票法是遇到相同的则票数 +1**，**遇到不同的则票数-1**，且**多数元素的个数 $> ⌊\frac{n}{2}⌋$**，**其余元素的个数总和 $\le ⌊\frac{n}{2}⌋$**，因此**多数元素的个数 - 其余元素的个数总和的结果一定 $\ge1$**，这就**相当于每个多数元素和其他元素的两两相互抵消**，**抵消到最后肯定还剩余至少 1 个多数元素**。

#### 2.3.2 参考代码

```java
/**
 * 169. 多数元素（版本 3：摩尔投票）
 * @param nums  数组
 * @return  数组中出现次数 大于 ⌊ n/2 ⌋ 的元素
 */
public int majorityElementV3(int[] nums) {
    int voteItem = 0, voteNum = 0;

for (int i = 0; i < nums.length; i++) {
        if (voteNum == 0) {
            voteItem = nums[i];
            voteNum = 1;
        }
        else if (voteItem == nums[i]) {
            voteNum++;
        } else {
            voteNum--;
        }
    }

return voteItem;
}
```

## 参考文献

1. [169. 多数元素](https://leetcode-cn.com/problems/majority-element)。
2. [ Java-3 种方法(计数法/排序法/摩尔投票法)](https://leetcode-cn.com/problems/majority-element/solution/3chong-fang-fa-by-gfu-2)。