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

Posted on | | reads times

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

题目描述

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

  • 数组中只有两种情况，是这个数字，不是这个数字，且若数字存在，则一定比其余数字出现次数的和大1或者更多，所以设置一个变量times初值为1，除了这个数字以外，其他数字一定会将times减到0，最终这个数字一定会出现。（如果存在的话）
  • 找到这个出现次数最多的数字，不一定是超过数组长度一半的数字，所以需要再统计该数字出现的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function MoreThanHalfNum_Solution(numbers)
{
    // write code here
    let res=numbers[0];
    let times=1;
    for(var i=0;i<numbers.length;i++){
        if(times===0){
            res=numbers[i]
        }else if(numbers[i]===res){
            times++;
        }else{
            times--;
        }
    }
    if(!countword(numbers,res)){
       return 0;
       }
    return res;
    
}
function countword(number,res){
    let time=0;
        for(var i=0;i<number.length;i++){
            if(number[i]===res)
            {
                time++;
            }
        }
    if(time*2<=number.length){
        return false;
    }
    return true;
}