牛客题解-NC73数组中超过一半的数字（众数）

发表于 更新于 分类于 阅读次数：

题目

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

示例1

输入：

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

输出：

1
2

思路

分析

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 思路：用一般的排序也可以完成这道题目，但是如果那样完成的话就可能太简单了。 用preValue记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count--，减到0的时候就要更换新的preValue值了，因为如果存在超过数组长度一半的值，那么最后preValue一定会是该值。

实现

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
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null||array.length == 0) return 0;
        int tmp = array[0];
        int count = 1;
        for(int i = 1; i<array.length; i++){
            if(array[i] == tmp){
                count++;
            }else{
                count--;
            }
            if(count == 0){
                tmp = array[i];
                count = 1;
            }
        }
        int sum = 0;
        for(int i = 0; i < array.length; ++i){
            if(array[i] == tmp){
                sum++;
            }
        }
        int res = 0;
        if(sum > array.length/2) res = tmp;
        return res;
    }
}