写点什么

找出数组中出现次数超过一半的数字

作者:zdd
  • 2022 年 1 月 04 日
  • 本文字数:413 字

    阅读完需:约 1 分钟

示例:

输入:[1,2,3,4,2,2,2]

输出:2


方法一

哈希表统计

遍历数组,用 HashMap 记录数字的个数;

方法二

排序取中位数

对数组进行排序,取中间的数字;

class Solution {    public int majorityElement(int[] nums) {        Arrays.sort(nums);        return nums[nums.length/2];    }}
复制代码

方法三

摩尔投票法

数组中的数字进行抵消,最后留下来的数字就是要找的数字。

[1,2,3,4,2,2,2]

1、假设要找的数字为 x=1,记录值为 cur=0

2、遍历数组,遇到 1,cur=cur+1=1,遇到 2,cur=cur-1=0

3、当 cur=0 时,x 为遍历数组的下一个值,x=3

4、重复上述步骤

最后剩下 x=2、cur=3,所以 2 就是要找的数字

class Solution {    public int majorityElement(int[] nums) {        int cur=0,x=0;        for(int i : nums){            if(cur==0) x=i;            cur+=i==x?1:-1;        }        return x;    }}
复制代码

注:前提是数组中存在这个数,否则要加验证,遍历数组,统计这个数字的个数,是否不小于数组的一半。

用户头像

zdd

关注

还未添加个人签名 2021.12.13 加入

还未添加个人简介

评论

发布
暂无评论
找出数组中出现次数超过一半的数字