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 时，进行如下操作：
1. 如果count==0，将x赋值给candidate，否则不更新candidate值
2. 如果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>>() {@Overridepublic 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>>() {
@Overridepublic int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {return o2.getValue().compareTo(o1.getValue());}});