LeetCode 之 JavaScript 解答第229題 —— 求眾數(shù) II（Majority E

BearyChat 發(fā)布于2019-08-23 16:45 / 2741人閱讀

摘要：繼續(xù)使用摩投票算法，假設(shè)要投票，選取票數(shù)超過以上選為候選人，一個(gè)被分為三等份，也就是說最多有兩位當(dāng)選人。排序解決先進(jìn)行一次排序快排，然后遍歷數(shù)據(jù)，找出滿足條件的數(shù)據(jù)。

Time：2019/4/5
Title: Majority Element 2
Difficulty: medium
Author: 小鹿

問題：Majority Element 2

Given an integer array of size n, find all elements that appear more than ? n/3 ? times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

solve:

▉ 算法思路：

1、上一篇是一個(gè)求超過 n/2 個(gè)數(shù)的數(shù)，采取的是用一個(gè)計(jì)數(shù)變量和計(jì)數(shù)元素變量來完成的。本篇題目是超過 n/3 的個(gè)數(shù)， 我們分別用兩個(gè)變量來完成，條件限制是時(shí)間復(fù)雜度是O(n),空間復(fù)雜度為O(1)。2、繼續(xù)使用摩投票算法，假設(shè)要投票，選取票數(shù)超過 n/3 以上選為候選人，一個(gè) n 被分為三等份，也就是說最多有兩位當(dāng)選人。
3、假設(shè)第一個(gè)人投甲，第二個(gè)投乙，甲、乙都站到臺上各個(gè)計(jì)數(shù)為 1 ，隨之第三個(gè)投甲，第四個(gè)投乙，計(jì)數(shù)分別加 1 ，第五個(gè)投丙，因?yàn)橹挥袃蓚€(gè)臺子，所以那就讓甲乙票數(shù)計(jì)數(shù)各減 1 ，當(dāng)甲、乙的票數(shù)分別減到 0 之后，第  m 個(gè)人投丙，就讓丙代替甲或已，繼續(xù)遍歷數(shù)據(jù)，直到遍歷完成為止。
4、上述只選擇出了那些有可能滿足條件的數(shù)據(jù)，下面對cm、cn存儲的數(shù)據(jù)做驗(yàn)證。

▉ 其他解法：

如果沒有題目中時(shí)間復(fù)雜度和空間復(fù)雜度的限制，有多種解決方法：1、散列表解決：先遍歷一遍數(shù)據(jù)，統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)，然后再遍歷一遍散列表，找出滿足條件的數(shù)字。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為 O(n)。
2、排序解決：先進(jìn)行一次排序（快排），然后遍歷數(shù)據(jù)，找出滿足條件的數(shù)據(jù)。時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)。

▉ 代碼實(shí)現(xiàn)：

      /**
        * @param {number[]} nums
        * @return {number[]}
        */
        var majorityElement = function(nums) {
            let [m,n,cm,cn,countm,countn] = [0,0,0,0,0,0];
            let result = [];
            
            for(let i = 0;i < nums.length; ++i){
                //m === nums[i]和n === nums[i]的判斷一定放到 cm === 0 和 cn === 0 之前，負(fù)責(zé)產(chǎn)生 bug。
                if(m === nums[i]){
                    cm ++;
                }else if(n === nums[i]){
                    cn ++;
                }else if(cm === 0){
                    m = nums[i];
                    cm ++;
                }else if(cn === 0){
                    n = nums[i];
                    cn ++;
                }else{
                    cn--;
                    cm--;
                }
            }
            //驗(yàn)證 cm、cn 存儲的數(shù)據(jù)
            for(let index in nums){
                if(nums[index] === m){
                    ++countm;
                }
                if(nums[index] === n){
                    ++countn;
                }
            }
            
            if(countm > Math.floor(nums.length/3)){
                result.push(m);
            }
        
            if(countn > Math.floor(nums.length/3) && n != m){
                result.push(n);
            }
            return result;
        };

        //測試
        let arr =[1,2,2,3,2,1,1,3];
        console.log(majorityElement(arr));

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅(jiān)持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...

歡迎關(guān)注我個(gè)人公眾號：「一個(gè)不甘平凡的碼農(nóng)」，記錄了自己一路自學(xué)編程的故事。