剑指offer 28.时间效率 数组中出现次数超过一半的数字

题目描述

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

 

解题思路

借助Map<Integer, Integer>，key为数字，value为数字出现的次数

 

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

/**
 
 * @author Transkai
 *
 */
public class MoreThanHalfNum_Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
         if (array.length==1) {
            return array[0];
        }
         Map<Integer, Integer> map=new HashMap<>();
         boolean flag=true;
         for(int i=0;i<array.length;i++) {
            for (Entry<Integer, Integer> map2:map.entrySet()) {
                if (array[i]==map2.getKey()) {
                    map.put(array[i], map.get(array[i])+1);    
                    flag=false;
                    if (map.get(array[i])>array.length/2) {
                        return array[i];
                    }
                }
                
            }
            if (flag) {
                map.put(array[i], 1);
            }
            
         }

         return 0;
            
        }
     public static void main(String[] args) {
         MoreThanHalfNum_Solution moreThanHalfNum_Solution=new MoreThanHalfNum_Solution();
         int[] array=new int[]{1,2,3,2,2,2,5,4,2};
         int a=moreThanHalfNum_Solution.MoreThanHalfNum_Solution(array);
         System.out.println(a);
    }
}