【剑指offer】数组中出现次数超过一半的数字

￡神魔★判官ぃ 2022-03-30 04:07 167阅读 0赞

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

## 题目描述 ##

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

## 解题思路 ##

*  巧解

import java.util.Arrays;
     
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            Arrays.sort(array);
            int count=0;
             
            for(int i=0;i<array.length;i++){
                if(array[i]==array[array.length/2]){
                    count++;
                }
            }
            if(count>array.length/2){
                return array[array.length/2];
            }else{
                return 0;
            }
             
        }
    }

*  用HashMap

import java.util.*;
    
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
            for(int i=0;i<array.length;i++){
                if(!map.containsKey(array[i])){
                    map.put(array[i],1);
                }else{
                    int count = map.get(array[i]);
                    map.put(array[i],++count);
                }
            }
            Iterator iter = map.entrySet().iterator();
            while(iter.hasNext()){
                Map.Entry entry = (Map.Entry)iter.next();
                Integer key =(Integer)entry.getKey();
                Integer val = (Integer)entry.getValue();
                if(val>array.length/2){
                    return key;
                }
            }
            return 0;
        }
    }