【問(wèn)題描述】[簡(jiǎn)單]

數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。示例 1:輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 輸出: 2限制：1 <= 數(shù)組長(zhǎng)度 <= 50000

【解答思路】

1. 哈希表統(tǒng)計(jì)法

哈希表統(tǒng)計(jì)法： 遍歷數(shù)組 nums ，用 HashMap 統(tǒng)計(jì)各數(shù)字的數(shù)量，最終超過(guò)數(shù)組長(zhǎng)度一半的數(shù)字則為眾數(shù)。此方法時(shí)間和空間復(fù)雜度均為 O(N)O(N) 。
時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(N）

public int majorityElement(int[] nums) {int n = nums.length;int max =1 ;int ans =nums[0];HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();for(int num :nums){if(map.containsKey(num)){map.put(num,map.get(num)+1);}else{map.put(num,1);}}for(int num: map.keySet()){if(map.get(num) > max){max = map.get(num) ;ans = num;}}return ans;} HashMap<Integer, Integer> map = new HashMap<>();for (int num : nums) {if (map.containsKey(num)) {map.put(num, map.getOrDefault(num, 0) + 1);} else {map.put(num, 1);}if (map.get(num) > nums.length / 2) {return num;}}return 0; }

2. 摩爾投票法 最佳

核心理念為 “正負(fù)抵消”



時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

public int majorityElement(int[] nums) {int x = 0, votes = 0;for(int num : nums){if(votes == 0) x = num;votes += num == x ? 1 : -1;}return x;}

3. 數(shù)組排序法

將數(shù)組 nums 排序，由于眾數(shù)的數(shù)量超過(guò)數(shù)組長(zhǎng)度一半，因此 數(shù)組中點(diǎn)的元素 一定為眾數(shù)。
時(shí)間復(fù)雜度：O(NlogN) 空間復(fù)雜度：O(1)

public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];}

【總結(jié)】

1.Java中HashMap遍歷幾種方式

2.HashMap常用語(yǔ)法

1.import java.util.HashMap;//導(dǎo)入;

2.HashMap<K, V> map=new HashMap<K, V>();//定義map，K和V是類(lèi)，不允許基本類(lèi)型;

3.void clear();//清空

4.put(K,V);//設(shè)置K鍵的值為V

5.V get(K);//獲取K鍵的值

6.boolean isEmpty();//判空

7.int size();//獲取map的大小

8.V remove(K);//刪除K鍵的值，返回的是V，可以不接收

9.boolean containsKey(K);//判斷是否有K鍵的值

10.boolean containsValue(V);//判斷是否有值是V

11.Object clone();//淺克隆，類(lèi)型需要強(qiáng)轉(zhuǎn)；如HashMap<String , Integer> map2=(HashMap<String, Integer>) map.clone();

3. 一題多解 熟悉掌握一種 其他掌握思想

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
參考鏈接：https://blog.csdn.net/gary0917/article/details/79783713
參考鏈接：https://www.cnblogs.com/shoulinniao/p/11966194.html

總結(jié)

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[39]题[数组中出现次数超过一半的数字][HashMap][摩尔投票法]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。