LeetCode总结 169多数元素和面试17.10 主要元素
这两道题都可以使用Boyer-Moore 投票算法。先说169简单题
169. 多数元素
题目：
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
解题思路
注意这里指的给定的数组总是存在多数元素，换句话说，测试用例中不可能出现【1,2,3】这样的例子。
解法一
最简单的是先排序，然后直接return数组的中间元素即可。就是求中位数的算法。
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
解法二
使用Boyer-Moore 投票算法。
Boyer算法基本思想：在每一轮投票过程中，从数组中删除两个不同的元素，知道投票过程无法继续位置，此时数组为空或者数组剩下的元素都相等。
说白点，就是抵消算法。知乎上讲的通俗明白，也就是刚开始的第一个数记为答案数或者成为candidate，然后设置更新状态count，开始遍历数组，当数组中接下来的数是candidate的话，count++，如果不是的话，就减减。到最后剩下的肯定就是数组中最多的数。
标准的leetcode解释：
Boyer-Moore 投票算法的步骤如下：
- 维护一个候选主要元素 candidate 和候选主要元素的出现次数 count，初始时 candidate 为任意值，count=0；
- 遍历数组 nums 中的所有元素，遍历到元素 x 时，进行如下操作：
- 如果count==0，将x赋值给candidate，否则不更新candidate值
- 如果x=candidate，则将count++，否则count--
- 遍历结束之后，如果数组nums中存在主要元素，则candidate为主要元素，否则candidate为数组的任意一个数字。
代码：
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
面试题 17.10. 主要元素
题目：
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5
示例 2：
输入：[3,2]
输出：-1
示例 3：
输入：[2,2,1,1,1,2,2]
输出：2
这道题跟上一道题的区别在于有可能没有主要元素，也就是数组中没有重复数字。
解法思路：
法一
首先应该能想到的就是HashMap的解法，将数组放到map中，然后一旦map中的数组某个元素个数超过数组长度的1/2，返回，否则返回-1；
代码：
//使用hash表完成，一旦元素超过hash表的一半，则说明找到了
HashMap<Integer, Integer> map = new HashMap<>();
for(int num:nums){
map.put(num, map.getOrDefault(num, 0)+1);
if(map.get(num)>nums.length/2){
return num;
}
}
return -1;
法二
跟一类似，首先将元素放到HashMap中，然后根据map的value降序排序成list，最后取出list中第一个元素的key值，如果第一个key值大于数组长度的2/1的话，直接返回，否则的话返回-1.
代码：
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
//根据map的value排序
List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return o2.getValue().compareTo(o1.getValue());
}
});
if (list.get(0).getValue() > nums.length / 2) {
return list.get(0).getKey();
}
return -1;
}
法三
也就是接续169多数元素之后的步骤：由于不一定存在主要元素，所以需要再遍历一遍数组，验证candidate是否是主要元素。
看代码吧：
package com.leetcode.everyday;
public class MajorityElement_2 {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for(int num:nums){
if (count==0){
candidate=num;
}
if(num==candidate){
count++;
}else{
count--;
}
}
//遍历数组，查找candidate的值出现的次数是否大于nums的数量
int ansCount = 0;
for(int num:nums){
if (num==candidate){
ansCount++;
}
}
if(ansCount*2>nums.length){
return candidate;
}else {
return -1;
}
}
public static void main(String[] args) {
int[] arr = {1,2,5,9,5,9,5,5,5};
System.out.println(new MajorityElement_2().majorityElement(arr));
}
}
还有小细节，count类型是包装类，是一种引用类型，所以可以赋值为null。
总结
-
掌握Boyer-Moore 投票算法。
-
再熟悉map根据value排序的算法：
//根据map的value排序 List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet()); list.sort(new Comparator<Map.Entry<Integer, Integer>>() { @Override public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) { return o2.getValue().compareTo(o1.getValue()); } });