数组中有一个数字出现的次数超过数组长度的一半

104 阅读 0 评论 69 点赞

我是靠谱客的博主大方糖豆，这篇文章主要介绍数组中有一个数字出现的次数超过数组长度的一半，现在分享给大家，希望可以做个参考。

题目：

数组中有一个数字出现的次数超过数组长度的一半。请找出这个数字。

解答：

 1 public class Solution {
 2 
 3     public int MoreThanHalfNum_Solution(int [] array) {
 4         if(array == null || array.length == 0) {
 5             return 0;
 6         }
 7         
 8         int result = array[0];
 9         int count = 1;
10 
11         for(int i = 1; i < array.length; i++) {
12             if(count == 0) {
13                 result = array[i];
14                 count = 1;
15             } else if(array[i] == result) {
16                 count++;
17             } else {
18                 count--;
19             }
20         }
21         
22 
23         if(isHalf(array, result)) {
24             return result;
25         } else {
26             return 0;
27         }
28 
29     }
30 
31     private static boolean isHalf(int[] array, int num) {
32         int count = 0;
33 
34         for(int i = 0; i < array.length; i++) {
35             if(array[i] == num) {
36                 count++;
37             }
38         }
39         
40         if(count > array.length / 2) {
41             return true;
42         } else {
43             return false;
44         }
45     }
46 }