题目概述(简单难度)
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
附上leetcode链接:
点击此处进入链接
思路与代码
思路展现
思路1(排序法)
排序法的思想其实非常简单,一个数组中出现次数最多的数字经过排序后,这个数组最中间的数字一定是这个出现次数最多的数字.
其实很容易证明,假设排序之后数组的中间值不是最多的元素,那么这个最多的元素要么是在数组前半部分,要么是在数组的后半部分,无论在哪,他的长度都不可能超过数组长度的一半。
代码示例
public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; }
时间复杂度:O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。
空间复杂度:O(logn)。如果使用语言自带的排序算法,需要使用 O(logn) 的栈空间。如果自己编写堆排序,则只需要使用 O(1)的额外空间。
思路2(摩尔投票法,最优解)
也是这道题目最经典的解法:使用摩尔投票法,摩尔投票法的思路是这样的:
假如我们有个职位,需要从 A,B 两位候选人中选出 先抽出一张票,投的是 A,我们在黑板上写着当前胜利者:A,票数:1 再抽出一张票,投的是 A,我们在黑板上写着当前胜利者:A,票数:2 再抽出一张票,投的是 B,用一张 B 抵消一张 A 的选票,我们在黑板上写着当前胜利者:A,票数:1 再抽出一张票,投的是 B,用一张 B 抵消一张 A 的选票,我们在黑板上写着当前胜利者:无,票数:0 再抽出一张票,投的是 A,我们在黑板上写着当前胜利者:A,票数:1 抽取完毕,恭喜 A 获胜,赢得该职位。
经过以上实例分析,我们可以得出 3个要点:
1:不同候选人的选票之间,可以一一抵消。
2:若当前胜利者存在多张选票时,不同的候选人的票,只能抵消一张当前胜利者的票。
3:若当前双方的选票被抵消为零,下一次抽出的候选人,将作为暂时的胜利者领先。
下面给出一位大佬的动画演示地址:非常清晰明了:
戳我戳我
代码示例
class Solution { public int majorityElement(int[] nums) { int major = nums[0]; int count = 1; for (int i = 1; i < nums.length; i++) { if (count == 0) { //前面都消完了,在重新赋值 count++; major = nums[i]; } else if (major == nums[i]) { //自己人,count就加1 count++; } else { //不是自己人就同归于尽,消掉一个 count--; } } return major; } }
时间复杂度:O(n) 摩尔投票法只对数组进行了一次遍历。
空间复杂度:O(1) 摩尔投票法只需要常数级别的额外空间。
总结
这道题目的常规算法有很多,举例如下:
1:哈希表(常用)
2:排序(常用)
3:位运算
4:摩尔投票法(最优解)
最经典的摩尔投票法希望大家能好好学习下,后续会将哈希的解法进行更新.