数组中出现次数超过一半的数字(简单难度)

简介: 数组中出现次数超过一半的数字(简单难度)

题目概述(简单难度)

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

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

示例 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:摩尔投票法(最优解)

最经典的摩尔投票法希望大家能好好学习下,后续会将哈希的解法进行更新.


相关文章
|
7月前
|
算法 Java
每日一题《剑指offer》数组篇之数组中出现次数超过一半的数字
每日一题《剑指offer》数组篇之数组中出现次数超过一半的数字
74 0
每日一题《剑指offer》数组篇之数组中出现次数超过一半的数字
【剑指offer】-数组汇总出现次数超过一半的数字-27/67
【剑指offer】-数组汇总出现次数超过一半的数字-27/67
剑指offer 40. 数组中出现次数超过一半的数字
剑指offer 40. 数组中出现次数超过一半的数字
81 0
剑指offer_数组---数组中出现次数超过一半的数
剑指offer_数组---数组中出现次数超过一半的数
54 0
|
算法 C++ Python
【每日算法Day 90】5种方法:求解数组中出现次数超过一半的那个数
【每日算法Day 90】5种方法:求解数组中出现次数超过一半的那个数
182 0
数组中数字出现的次数(中等难度)
数组中数字出现的次数(中等难度)
98 0
数组中数字出现的次数(中等难度)
|
C++
13.数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
71 0
数组中数字出现的次数 II(简单难度)
数组中数字出现的次数 II(简单难度)
105 0
|
算法
【刷算法】数组中出现次数超过一半的数字
【刷算法】数组中出现次数超过一半的数字