【LeetCode】剑指 Offer 39. 数组中出现次数超过一半的数字 p205 -- Java Version

题目链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

1. 题目介绍（39. 数组中出现次数超过一半的数字）

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

【测试用例】：
示例1：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

【条件约束】：

提示：

• 1 <= 数组长度 <= 50000

【相关题目】：

注意：本题与主站 169. 多数元素 题目相同。

2. 题解

2.1 暴力穷举 – O(n²)

时间复杂度O(n²)，空间复杂度O(n)

【解题思路】：
对于排序数组，我们可以很容易统计出每个数字出现的次数，可参考 剑指 Offer 53 - I. 在排序数组中查找数字 I ，然后再对次数进行判断，看是哪个数字出现的次数超过了数组长度的一半。
……
【实现策略】：

1. 对输入数组 nums 使用 sort() 方法进行升序排序；
   【sort()方法详解】：详述Java中sort排序函数
2. 定义一个 HashMap 用来记录每个数字在数组中出现的次数，数组中数组为键，出现的次数为值；
   【注意点】：HashMap 的键虽然不能重复，但是如果是有重复键的键值对要加入，那么 新值会覆盖掉旧值，切记！
3. 双循环穷举，当然下面为了提高效率，同时防止重复键值对被覆盖，通过每次循环中把 j 赋值给 i 的操作，这样就保证了内循环结束后，i 位于当前重复数字的末尾，而由于循环结束，i++ 的原因，这样就相当于间接的移动 i 到了下一个非重复数组数字的位置，然后进行下一个数字重复次数的统计；（这里的双循环穷举，可以改为 一次遍历 + 二分查找（找左右边界） 的方式，进一步提高统计效率）
4. 最后，遍历 HashMap，找出次数超过数组一半的数字并返回。

class Solution {public int majorityElement(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 遍历数组// 定义map用来记录每个数字在数组中出现的次数HashMap<Integer,Integer> map = new HashMap<>();int n = 0;for(int i = 0; i < nums.length; i++){for (int j = i; j < nums.length; j++){if (nums[j] == nums[i]) {n++;i = j; // 将i移到下一个数的位置} }map.put(nums[i],n);n = 0;}// 遍历map，找出超过一半数组长度的数字for(Map.Entry<Integer,Integer> entry : map.entrySet()){if (entry.getValue() > nums.length/2) return entry.getKey();}return 0;}
}

代码简化：

【实现策略】：
看了题解，意识到自己傻冒了，忘了 HashMap 中有 containsKey() 方法了，那么完全可以直接一次遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 ，根本不用双循环，一个一个对比，直接单次循环， containsKey(下一个数字) ，有就++，没有就移动到下一个就完了，此方法时间和空间复杂度均为 O(n) 。

1. 一次遍历，在遍历的过程中将数组数字存入 HashMap ；
2. 判断 HashMap 的键是否已有当前数字，有就加1，没有就下一个。

……
但是不知道为啥，这样好慢，比没简化的代码要慢的多，估计应该是力扣的测试用例设置的不太好。

class Solution {public int majorityElement(int[] nums) {// 遍历数组// 定义map用来记录每个数字在数组中出现的次数HashMap<Integer,Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++){if (!map.containsKey(nums[i])) map.put(nums[i],1);else map.put(nums[i], map.get(nums[i])+1);}// 遍历map，找出超过一半数组长度的数字for(Map.Entry<Integer,Integer> entry : map.entrySet()){if (entry.getValue() > nums.length/2) return entry.getKey();}return 0;}
}

2.2 数组排序法 – O(nlogn)

时间复杂度O(nlogn)，空间复杂度O(1)

【解题思路】：
将数组 nums 排序，数组中点的元素 一定为众数。
根据题目所出的数组特性：数组中有一个数字出现的次数超过了数组长度的一半，那么如果对这个数组进行排序，排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。
……
【实现策略】：
根据上面的思路，代码就变的异常的轻松加愉快：

1. 排序
2. 返回数组的中点数字

……
当然如果返回值一变，要求返回该数字的重复次数，这个方法就趴菜了，不过题目摇身一变就变成了剑指 Offer 53 - I. 在排序数组中查找数字 I ，可用 2.1 中的方法解决。

class Solution {public int majorityElement(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 遍历数组return nums[nums.length/2];}
}

2.3 摩尔投票法（原书题解2） – O(n)

时间复杂度O(n)，空间复杂度O(1)

【解题思路】：
核心理念为 票数正负抵消，因为题目中明确的指出了，要返回的数字是在数组中出现次数超过一半的数字，那么通过正负抵消，最后能留下的一定是该数字。
推论一： 若记 众数 的票数为 +1，非众数 的票数为 -1，则一定有所有数字的 票数和 >0 ；
推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。

……
【实现策略】：

1. 定义 x 存储众数（候选人），定义票数 votes；
2. 一次遍历，判断当前票是否是给当前候选人的，如果是则加1，如果不是则减1，当候选人的票数为0时，则更换新的候选人。

……
【唠叨两句】：
原书题解1 采用了快排思想的排序方法 Partition() ，一直到 Partition() 方法随机到中点，即，将比中点数小的数字移到数组的左边，比中点数大的数组移到数组的右边。此方法可以，但没必要，除非题目要求不能使用库函数，不然感觉倒是没必要自己写排序，

class Solution {public int majorityElement(int[] nums) {int x = 0, votes = 0, count = 0;for(int num : nums){if(votes == 0) x = num;votes += num == x ? 1 : -1;}// 验证 x 是否为众数for(int num : nums)if(num == x) count++;return count > nums.length / 2 ? x : 0; // 当无众数时返回 0}
}

3. 参考资料

[1] 剑指 Offer 39. 数组中出现次数超过一半的数字（摩尔投票法，清晰图解）
[2] Java遍历Map的几种方法
[3] 【Java】 剑指offer(53-1) 数字在排序数组中出现的次数