【题39】数组中出现次数超过一半的数字

清疚 2022-03-08 10:04 141阅读 0赞

【题目】  
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。  
【思路】  
**解法一**：特性：数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组一半的数字。即这个数字是统计学上的中位数。  
**解法二**：可以理解为它出现的次数比其他数字出现次数的和还要多。  
便利数组的时候保存两个值：数组中的一个数组和次数。  
遍历时：  
如果和之前保存的数字相同，则次数加1，  
如果下一个数字和我们之前的数字不同，则次数减1，  
如果次数为0，需要保存下一个数字，并把次数设为1.  
由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字  
【实现】

import java.util.Arrays;
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            int n = array.length;
            if(n ==0){
                return 0;
            }
            int count =0;
            Arrays.sort(array);
            int num = array[n/2];
            for(int i  = 0;i < n;i++){
                if(num == array[i]){
                    count++;
                }
            }
            if(count <=(n/2)){
                num = 0;
            }
            return num;
        }
    }

参考  
1.《剑指offer》