国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發(fā)設計 > 正文

Leetcode: Majority Element

2019-11-14 22:19:14
字體:
來源:轉載
供稿:網(wǎng)友
Leetcode: Majority Element
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.

Leetcode的官方答案給的解答很好,我的方法是HashMap. 除了brute force和sorting常見方法以外,還有幾個方法,思路都還不錯,1是我的方法,我覺得2、4、5都是不錯的思路。

  1. Runtime: O(n), Space: O(n) — Hash table: Maintain a hash table of the counts of each element, then find the most common one.
  2. Average runtime: O(n), Worst case runtime: Infinity — Randomization: Randomly pick an element and check if it is the majority element. If it is not, do the random pick again until you find the majority element. As the PRobability to pick the majority element is greater than 1/2, the expected number of attempts is < 2.
  3. Runtime: O(nlogn) — Divide and conquer: Divide the array into two halves, then find the majority element A in the first half and the majority element B in the second half. The global majority element must either be A or B. If A == B, then it automatically becomes the global majority element. If not, then both A and B are the candidates for the majority element, and it is suffice to check the count of occurrences for at most two candidates. The runtime complexity, T(n) = T(n/2) + 2n= O(nlogn).
  4. Runtime: O(n) — Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x:
    1. If the counter is 0, we set the current candidate to x and the counter to 1.
    2. If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate.
    After one pass, the current candidate is the majority element. Runtime complexity = O(n).
  5. Runtime: O(n) — Bit manipulation: We would need 32 iterations, each calculating the number of 1's for the ithbit of allnnumbers. Since a majority must exist, therefore, either count of 1's > count of 0's or vice versa (but can never be equal). The majority number’s ithbit must be the one bit that has the greater count.
 1 public class Solution { 2     public int majorityElement(int[] num) { 3         int n = num.length; 4         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 5         for (int elem : num) { 6             if (map.containsKey(elem)) { 7                 map.put(elem, map.get(elem)+1); 8             } 9             else {10                 map.put(elem, 1);11             }12         }13         for (int item : map.keySet()) {14             if (map.get(item) > n/2) {15                 return item;16             }17         }18         return -1;19     }20 }


發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 涞源县| 景德镇市| 大新县| 定日县| 公安县| 鄂州市| 永定县| 宿松县| 云南省| 蓬莱市| 平远县| 芒康县| 巴中市| 大邑县| 东源县| 鹤峰县| 溆浦县| 方正县| 车致| 罗定市| 叙永县| 紫阳县| 将乐县| 长武县| 扎赉特旗| 大洼县| 嘉祥县| 印江| 玉环县| 黎城县| 二连浩特市| 南宁市| 辉南县| 突泉县| 兴和县| 织金县| 遵义市| 兴安县| 巨野县| 揭西县| 读书|