【刷算法】数组中出现次数超过一半的数字

Lin_R 发布于2019-08-23 10:27 / 1580人阅读

摘要：题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。如果不存在则输出。分析像这样的数组，如果每次去掉两个不同的数字，那么到最后会剩下，就是数组中超过一半的数字。可以使用代码来模拟这个过程即可。

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

分析

像[1,2,3,2,2,2,5,4,2]这样的数组，如果每次去掉两个不同的数字，那么到最后会剩下[2]，2就是数组中超过一半的数字。可以使用代码来模拟这个过程即可。

代码实现

function MoreThanHalfNum_Solution(numbers)
{
    if(numbers.length === 0)
        return 0;
    if(numbers.length === 1)
        return numbers[0];
    
    var times = 0, cand;
    
    for(var i = 0;i < numbers.length;i++) {
        if(times === 0){
            cand = numbers[i];
            times = 1;
        } else {
            if(cand === numbers[i])  
                times++;
            else 
                times--;
        }
    }
    
    times = 0;
    for(var i = 0;i < numbers.length;i++) {
        if(cand === numbers[i])
            times++;
    }
    if(times > Math.floor(numbers.length/2))
        return cand;
    else
        return 0;
}

GPU云服务器云服务器数组中未出现的数字数组中出现多次数据出现次数统计 php统计出现次数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96362.html

剑指offer中的算法题(PHP版)

摘要：二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。解法有两种，一种是递归法，一种是迭代法但是递归法计算的时间复杂度是以的指数的方式递增的，如果面试中千万不要用递归法，一定要用迭代法。二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和...

big_cat 2019-06-27 15:43 评论0 收藏0
面试题39：数组中出现次数超过一半的数字

摘要：面试题数组中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半，找出这个数字。面试题39：数组中出现次数超过一半的数字数组中有一个数字出现的次数...

Eminjannn 2021-11-15 11:38 评论0 收藏0
❤️思维导图整理大厂面试高频数组9: 删除重复元素的通解问题, 力扣26/80❤️

此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...

MasonEast 2021-09-04 16:40 评论0 收藏0
【刷算法】整数中1出现的次数（从1到n整数中1出现的次数）

摘要：题目描述求出的整数中出现的次数并算出的整数中出现的次数为此他特别数了一下中包含的数字有因此共出现次但是对于后面问题他就没辙了。希望你们帮帮他并把问题更加普遍化可以很快的求出任意非负整数区间中出现的次数从到中出现的次数。题目描述求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6...

Shisui 2019-08-23 10:29 评论0 收藏0
一道有意思的面试算法题

摘要：解决方案异或操作异或运算是对于二进制数字而言的，比如说一个有两个二进制，如果两个值不相同，则异或结果为。比如说，本质上其实是和的每一对比特位执行异或操作，等价于下面数字对应的二进制数字对应的二进制数字对应的二进制因此的结果就为啦。新年第一篇文章，先祝大家新年快乐！！那么接下来进入正文。前言前阵子突发奇想，突然开始刷leetcode。其中刷到了一道有意思的题目，发现这道题是当时秋招...

maxmin 2019-08-23 14:28 评论0 收藏0