Majority Element I

Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.

You may assume that the array is non-empty and the majority element always exist in the array.

哈希表法

復雜度

時間 O(N) 空間 O(N)

思路

在遍歷數(shù)組的過程中，用一個哈希表記錄每個數(shù)出現(xiàn)過的次數(shù)，如果該次數(shù)大于一半，則說明是眾數(shù)。

排序法

復雜度

時間 O(NlogN) 空間 O(1)

思路

將數(shù)組排序，這時候數(shù)組最中間的數(shù)肯定是眾數(shù)。

代碼

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

位操作法

復雜度

時間 O(N) 空間 O(1)

思路

假設一個數(shù)是最多只有32位的二進制數(shù)，那么我們從第一位到第32位，對每一位都計算所有數(shù)字在這一位上1的個數(shù)，如果這一位1的個數(shù)大于一半，說明眾數(shù)的這一位是1，如果小于一半，說明大多數(shù)的這一位是0。

投票法

復雜度

時間 O(N) 空間 O(1)

思路

記錄一個candidate變量，還有一個counter變量，開始遍歷數(shù)組。如果新數(shù)和candidate一樣，那么counter加上1，否則的話，如果counter不是0，則counter減去1，如果counter已經(jīng)是0，則將candidate更新為這個新的數(shù)。因為每一對不一樣的數(shù)都會互相消去，最后留下來的candidate就是眾數(shù)。

代碼

public class Solution {public int majorityElement(int[] nums) {int candidate = nums[0], cnt = 0;for(int i = 1; i < nums.length; i++){if(candidate == nums[i]){cnt++;} else if(cnt==0){candidate = nums[i];} else {cnt--;}}return candidate;} }

Majority Element II

Given an integer array of size n, find all elements that appear more than ? n/3 ? times. The algorithm should run in linear time and in O(1) space.

投票法

復雜度

時間 O(N) 空間 O(1)

思路

上一題中，超過一半的數(shù)只可能有一個，所以我們只要投票出一個數(shù)就行了。而這題中，超過n/3的數(shù)最多可能有兩個，所以我們要記錄出現(xiàn)最多的兩個數(shù)。同樣的兩個candidate和對應的兩個counter，如果遍歷時，某個候選數(shù)和到當前數(shù)相等，則給相應計數(shù)器加1。如果兩個計數(shù)器都不為0，則兩個計數(shù)器都被抵消掉1。如果某個計數(shù)器為0了，則將當前數(shù)替換相應的候選數(shù)，并將計數(shù)器初始化為1。最后我們還要遍歷一遍數(shù)組，確定這兩個出現(xiàn)最多的數(shù)，是否都是眾數(shù)。

代碼

public class Solution {public List<Integer> majorityElement(int[] nums) {List<Integer> res = new ArrayList<Integer>();if(nums.length == 0) return res;int c1 = 1, c2 = 0, n1 = nums[0], n2 = 0;for(int i = 1; i < nums.length; i++){// 如果和某個候選數(shù)相等，將其計數(shù)器加1if(nums[i] == n1){c1++;} else if(nums[i] == n2){c2++;// 如果都不相等，而且計數(shù)器都不為0，則計數(shù)器都減1} else if(c1 != 0 && c2 != 0){c1--;c2--;// 如果某個計數(shù)器為0，則更新相應的候選數(shù)} else {if(c1 == 0){n1 = nums[i];c1 = 1;} else {n2 = nums[i];c2 = 1;}}}c1 = 0;c2 = 0;for(int i = 0; i < nums.length; i++){if(nums[i] == n1) c1++;else if(nums[i] == n2) c2++;}if(c1 > nums.length / 3) res.add(n1);if(c2 > nums.length / 3) res.add(n2);return res;} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的[Leetcode] Majority Element 众数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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