力扣经典算法篇-5-多数元素（哈希统计，排序，摩尔投票法）

题干：
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：nums = [3,2,3]
输出：3

示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

解题：
（1）、哈希统计法
定义一个hash接口，如HashMap，统计每个元数出现的次数。之后在遍历HashMap获取次数最大的元素即可。这个方法是最容易想到，且最通用的方法。
代码示例：（java）

public static int majorityElement(int[] nums) {if (nums.length == 1) {return nums[0];}Map<Integer, Integer> map = new HashMap<>();      // 统计元素出现的次数for (int i = 0; i < nums.length; i++) {map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);}int count = 0;         // 暂存出现最大的次数int key = nums[0];      // 最大次数对应的元素值for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if (entry.getValue() > count) {key = entry.getKey();count = entry.getValue();}}return key;}

（2）、排序法
因为题干要说明了超过n/2的元素。所以对数组排序后，众数一定会在最中间的位置。
可以结合上面参考的几个示例，在有序和无序的情况下，自己思考一下。
代码示例：

public static int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}

（3）、摩尔投票法
摩尔投票法的核心理念为 票数正负抵消 。
推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。
推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。

思考一下：

• 当候选元素为众数时，根据推论一遇到众数+1，非众数-1，结果一定大于0，因为众数至少超过了n/2。
• 当候选元素不是众数时，先不考虑其他元素的影响，仅众数的影响就可以将这个候选元素递减到0，而且最终剩余的数组中肯定还是众数出现的次数最多。
  （前面递减的过程理解下：最坏也是消除同等数量的众数和普通元素，剩余的部分肯定还是众数多，听到这里，想明白了没？^_）

代码示例：

public static int majorityElement(int[] nums) {int temp = 0;int votes = 0;for (int i = 0; i < nums.length; i++) {if (votes == 0) {temp = nums[i];}votes += (temp == nums[i] ? 1 : -1);}return temp;}

逆风翻盘，Dare To Be！！！