摘要:排序法復雜度時間空間思路將數組排序,這時候數組最中間的數肯定是眾數。投票法復雜度時間空間思路記錄一個變量,還有一個變量,開始遍歷數組。代碼投票法復雜度時間空間思路上一題中,超過一半的數只可能有一個,所以我們只要投票出一個數就行了。
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)
思路在遍歷數組的過程中,用一個哈希表記錄每個數出現過的次數,如果該次數大于一半,則說明是眾數。
排序法 復雜度時間 O(NlogN) 空間 O(1)
思路將數組排序,這時候數組最中間的數肯定是眾數。
代碼public class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; } }位操作法 復雜度
時間 O(N) 空間 O(1)
思路假設一個數是最多只有32位的二進制數,那么我們從第一位到第32位,對每一位都計算所有數字在這一位上1的個數,如果這一位1的個數大于一半,說明眾數的這一位是1,如果小于一半,說明大多數的這一位是0。
投票法 復雜度時間 O(N) 空間 O(1)
思路記錄一個candidate變量,還有一個counter變量,開始遍歷數組。如果新數和candidate一樣,那么counter加上1,否則的話,如果counter不是0,則counter減去1,如果counter已經是0,則將candidate更新為這個新的數。因為每一對不一樣的數都會互相消去,最后留下來的candidate就是眾數。
代碼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)
思路上一題中,超過一半的數只可能有一個,所以我們只要投票出一個數就行了。而這題中,超過n/3的數最多可能有兩個,所以我們要記錄出現最多的兩個數。同樣的兩個candidate和對應的兩個counter,如果遍歷時,某個候選數和到當前數相等,則給相應計數器加1。如果兩個計數器都不為0,則兩個計數器都被抵消掉1。如果某個計數器為0了,則將當前數替換相應的候選數,并將計數器初始化為1。最后我們還要遍歷一遍數組,確定這兩個出現最多的數,是否都是眾數。
代碼public class Solution { public ListmajorityElement(int[] nums) { List res = new ArrayList (); if(nums.length == 0) return res; int c1 = 1, c2 = 0, n1 = nums[0], n2 = 0; for(int i = 1; i < nums.length; i++){ // 如果和某個候選數相等,將其計數器加1 if(nums[i] == n1){ c1++; } else if(nums[i] == n2){ c2++; // 如果都不相等,而且計數器都不為0,則計數器都減1 } else if(c1 != 0 && c2 != 0){ c1--; c2--; // 如果某個計數器為0,則更新相應的候選數 } 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; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64506.html
摘要:小鹿題目算法思路摩爾投票算法題目的要求是讓我們求數組中超過一半數據以上相同的元素且總是存在的。 Time:2019/4/4Title: Majority Element 1Difficulty: easyAuthor: 小鹿 題目:Majority Element 1 Given an array of size n, find the majority element. The ...
摘要:因為眾數出現的次數必定大于,所以我們只要取第個位置上的元素,這個元素一定為我們要找的眾數。 題目詳情 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 th...
摘要:繼續使用摩投票算法,假設要投票,選取票數超過以上選為候選人,一個被分為三等份,也就是說最多有兩位當選人。排序解決先進行一次排序快排,然后遍歷數據,找出滿足條件的數據。 Time:2019/4/5Title: Majority Element 2Difficulty: mediumAuthor: 小鹿 問題:Majority Element 2 Given an integer ar...
摘要:在線網站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目,語言 JavaScript。 在線網站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...
摘要:當時題目改成了小明收紅包,找出現次數超過一般的那個紅包,要求線性時間復雜度,也就是說不能用排序排序算法最優情況是。另外這個題在上的難度是哦,好傷心啊,當初的我連這題都沒想出解法,真是夠年輕啊。 169. Majority Element Given an array of size n, find the majority element. The majority element i...
閱讀 3159·2021-10-14 09:42
閱讀 3564·2019-08-26 13:56
閱讀 3444·2019-08-26 11:59
閱讀 938·2019-08-23 18:00
閱讀 2196·2019-08-23 17:51
閱讀 3522·2019-08-23 17:17
閱讀 1479·2019-08-23 15:11
閱讀 5145·2019-08-23 15:05