题目描述
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
数据结构
- 数组
算法思维
- 遍历、计数、摩尔投票法
解题思路
一. Comprehend 理解题意
- 数组中至少有 length/2 +1 个相同的元素，这个元素即为“多数元素”
- 用遍历的方式找出数组中的“多数元素”
二. Choose 选择数据结构与算法
计数法
- 数据结构：数组
- 算法思维：遍历、计数
- 解题思路
元素每出现一次就 计数 +1
不断判断计数是否 > n/2
三. Code 编码实现基本解法
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
int count = map.getOrDefault(num, 0) + 1;
//超过一半，则直接返回
if (count > nums.length / 2) {
return num;
}
map.put(num, count);
}
return -1;
}
}
执行耗时：14 ms，击败了 27.94% 的Java用户
内存消耗：43.7 MB，击败了 22.77% 的Java用户
时间复杂度：O(n)
• 原数组遍历 O(n)
• map 集合的读取和存入 O(n)
空间复杂度：O(n)
• map 集合最多需要 O(n/2) 的内存空间
四. Consider 思考更优解
改变算法思维：摩尔投票法 / “盯人战术”
- 数组中的每个元素都有一张选票
- 每个元素都和当前的“冠军元素”比较，如果相同则给冠军元素（即自己）投赞成票，如果不同则投反对票
- 开始时以第一个元素为冠军元素，每当反对票超过赞成票时，冠军易主
- 由于多数元素控制着半数以上的选票，比任何其他元素的选票加起来都多，因此无论投票顺序如何，最终多数元素都会胜选
- 遍历结束时的“冠军元素”即为数组中的多数元素
五. Code 编码实现最优解
class Solution {
public int majorityElement(int[] nums) {
//1.投票开始前，以第一个元素为冠军，它拥有自己的一张赞成票
int champion = nums[0];
int votes = 1;
//2.所有元素逐一投票
for(int i=1; i<nums.length; i++){
//3.如果是“自己人”就投赞成票
if (nums[i] == champion) votes++;
//4.如果不是“自己人”就投反对票
else votes--;
//5.当反对票多于赞成票，冠军易主为当前投票者，其初始赞成票数为1
if (votes == -1){
champion = nums[i];
votes = 1;
}
}
//6.最终胜选的即为多数元素
return champion;
}
}
执行耗时：1 ms，击败了 99.99% 的Java用户
内存消耗：41.9 MB，击败了 44.00% 的Java用户
时间复杂度：O(n)
• 原数组遍历 O(n)
空间复杂度：O(1)
• 两个整型变量，常数级内存空间 O(1)
六. Change 变形与延伸
=== 待续 ===
