2018-09-23 13:25:40

主元素問題是一個非常經典的問題，一般來說，主元素問題指的是數組中元素個數大于一半的數字，顯然這個問題可以通過遍歷計數解決，時間復雜度為O(n)，空間復雜度為O(n)。這樣的算法有兩個弊端，一是空間復雜度較高，二是沒法處理數據流問題。

因此就有了Boyer-Moore Majority Vote algorithm，這個算法可以用來高效的解決主元素問題，并且空間復雜度降到了O(1)，時間復雜度保持不變。

算法的思路就是將不同的元素進行抵消，最后剩余的就是最終的結果。

如果說題目中沒有明確說明一定存在主元素，那么還需要額外一次遍歷來確認當前的解為主元素。

一、主元素問題

問題描述：

問題求解：

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

?

二、Follow Up

問題描述：

問題求解：

    public List<Integer> majorityElement(int[] nums) {if (nums == null || nums.length == 0) return new ArrayList<>();int candidate1 = 0;int candidate2 = 0;int count1 = 0;int count2 = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] == candidate1) count1++;else if (nums[i] == candidate2) count2++;else if (count1 == 0) {candidate1 = nums[i];count1 = 1;}else if (count2 == 0) {candidate2 = nums[i];count2 = 1;}else {count1--;count2--;}}List<Integer> res = new ArrayList<>();count1 = 0;count2 = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] == candidate1) count1++;else if (nums[i] == candidate2) count2++;}if (count1 > nums.length / 3) res.add(candidate1);if (count2 > nums.length / 3) res.add(candidate2);return res;}

?

轉載于:https://www.cnblogs.com/TIMHY/p/9692531.html

總結

以上是生活随笔為你收集整理的主元素问题 Majority Element的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。