題目描述
給定一個(gè)大小為 n 的數(shù)組，找到其中的眾數(shù)。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在眾數(shù)。

示例 1:

輸入: [3,2,3] 輸出: 3

示例 2:

輸入: [2,2,1,1,1,2,2] 輸出: 2

思路：

數(shù)組先排序，然后取length/2的元素。時(shí)間復(fù)雜度：O(nlog(n))，空間復(fù)雜度O(1)

摩爾投票法。時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度O(1)

使用Map保存每個(gè)元素的計(jì)數(shù)，然后遍歷Map取計(jì)數(shù)最大值。時(shí)間復(fù)雜度：O(nlog(n))，空間復(fù)雜度O(n)

思路1實(shí)現(xiàn)代碼：

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

思路2，摩爾投票法是統(tǒng)計(jì)占多數(shù)票的算法。

參考博客：https://blog.csdn.net/tfcy694/article/details/82717808
對應(yīng)實(shí)現(xiàn)代碼如下：

/*** 摩爾投票算法* @param nums* @return*/public int majorityElement(int[] nums) {int res = nums[0];int count=1;for(int i=1;i<nums.length;i++) {if(res == nums[i]) {count++;}else {count--;if(count ==0) {res=nums[i];count=1;}}}return res;}

思路3也很簡單，代碼就不貼出來了

總結(jié)

以上是生活随笔為你收集整理的2019-03-11-算法-进化（求众数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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