題目描述

數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出2。 分析：找數組中出現次數超過一半的數字，我們一半可以采用兩種方法，一是使用快排，對數組進行排序，然后直接輸出排序數組中間位置的數。第二種是使用HashMap<Integer,Integer>,key是數組中的數字，value為其在數組中出現的次數，順序掃描數組，記錄下數組出現的次數，輸出大于數組長度一半的value值對應的key值。 第一種方法代碼很簡單，此處不表，第二種方法的代碼如下： 1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.Collection; 4 import java.util.HashMap; 5 import java.util.Set; 6 7 public class Solution { 8 public int MoreThanHalfNum_Solution(int [] array) { 9 if(array==null||array.length==0){ 10 return 0 ; 11 } 12 if(array.length==1){ 13 return array[0] ; 14 } 15 int most=0 ; 16 HashMap<Integer,Integer> m = new HashMap<Integer,Integer>() ; 17 for(int i = 0 ; i < array.length ;i++){ 18 if(!m.containsKey(array[i])){ 19 m.put(array[i], 1) ; 20 } 21 else{ 22 int temp = m.get(array[i]); 23 m.put(array[i], temp+1) ; 24 } 25 26 } 27 Set<Integer> a = m.keySet() ; 28 for(int temp : a){ 29 if(m.get(temp)>(array.length/2)){ 30 most = temp ; 31 } 32 } 33 return most ; 34 } 35 }

?

轉載于:https://www.cnblogs.com/huntertoung/p/4803147.html

總結

以上是生活随笔為你收集整理的【剑指offer】十九，数组中出现次数超过一半的数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。