题目描述

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

代码一

  1. public class Solution {
  2.     public static void main(String[] args)
  3.     {
  4.         int[] arr = new int[] {1,2,2,2,2,2,5,3,3};
  5.         System.out.println(MoreThanHalfNum_Solution(arr));
  6.     }
  7.     public static int MoreThanHalfNum_Solution(int [] array) {
  8.         if(array.length==0)
  9.         {
  10.             return 0;
  11.         }
  12.         HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
  13.         for(int i = 0;i<array.length;i++)
  14.         {
  15.             if(!hash.containsKey(array[i])){
  16.                    hash.put(array[i],1);
  17.             }else
  18.             {
  19.                 hash.put(array[i],hash.get(array[i])+1);
  20.             }
  22.         }
  23.         for(int key : hash.keySet())
  24.         {
  25.             if(hash.get(key)>array.length/2)
  26.             {
  27.                 return key;
  28.             }
  29.         }
  30.         return 0;
  31.     }
  32. }

代码二

思路：

用一般的排序也可以完成这道题目，但是如果那样完成的话就可能太简单了。
用preValue记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count—，减到0的时候就要更换新的preValue值了，因为如果存在超过数组长度一半的值，那么最后preValue一定会是该值。

  1. public class Solution {
  2.     public int MoreThanHalfNum_Solution(int [] array) {
  3.         if(array == null || array.length == 0)return 0;
  4.         int preValue = array[0];//用来记录上一次的记录
  5.         int count = 1;//preValue出现的次数（相减之后）
  6.         for(int i = 1; i < array.length; i++){
  7.             if(array[i] == preValue)
  8.                 count++;
  9.             else{
  10.                 count--;
  11.                 if(count == 0){
  12.                     preValue = array[i];
  13.                     count = 1;
  14.                 }
  15.             }
  16.         }
  17.         int num = 0;//需要判断是否真的是大于1半数，这一步骤是非常有必要的，因为我们的上一次遍历只是保证如果存在超过一半的数就是preValue，但不代表preValue一定会超过一半
  18.         for(int i=0; i < array.length; i++)
  19.             if(array[i] == preValue)
  20.                 num++;
  21.         return (num > array.length/2)?preValue:0;
  23.     }
  24. }

代码三

  1. public int MoreThanHalfNum_Solution(int [] array) {
  2.     Arrays.sort(array);
  3.     int i=array[array.length/2];
  4.     return IntStream.of(array).filter(k->k==i).count()>array.length/2?i:0;
  5. }

实用技巧

  • Arrays.sort(array);可以对数组进行排序
  • Stream实例.filter(过滤规则)可对流中的数据进行筛选