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

题目描述

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

 1 /**
 2  * 
 3  * @author gentleKay
 4  * 题目描述
 5  * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 6  * 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
 7  * 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
 8  * 如果不存在则输出0。
 9  */
10 
11 public class Main28{
12 
13     public static void main(String[] args) {
14         // TODO Auto-generated method stub
15         int[] array = {2,1,2,3,2,4,2,5,2,3,2};
16         int num = Main28.MoreThanHalfNum_Solution(array);
17         System.out.println(num);
18     }
19     
20     public static int MoreThanHalfNum_Solution(int [] array) {
21         int len = array.length;
22         if (len == 0) {
23             return 0;
24         }
25         
26         int num = array[0];
27         int count = 1;
28         for (int i=1;i<array.length;i++) {
29             if (array[i] == num) {
30                 count++;
31             }else {
32                 count--;
33             }
34             if (count == 0) {
35                 num = array[i];
36                 count = 1;
37             }
38         }
39         
40         count = 0;
41         for (int i=0;i<array.length;i++) {
42             if (num == array[i])
43                 count++;
44         }
45         if (count *2 > len) {
46             return num;
47         }
48         return 0;
49     }
50 }