找出超过半数的那个数字

一、问题描述

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

二、解题思路

      1) 思路一（最简洁）：

                       根据鸽笼原理，最差情况下，也会出现三个“该数字”连续排在一起，定义变量count，如果左右数据相同，

count++，并保存该数据。

                      

                       如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。

                       
       2) 思路二（最常规）：

                       通过Java自带的排序工具，将从小到大排序，中位数既是所求值。

                       
       3) 思路三（最简单）：

                       通过map，统计出现的最多值。

                       

三、注意事项

       1) 若数组中不含这类数据怎么处理？进行数据验证。

       

四、代码实现

        见我的github：找出超过半数的那个数字