LeetCode 169. Majority Element

LeetCode 169. Majority Element

題目描述

題目鏈接

思路1 Hash表

很直接,程式碼略
由於題目的follow-up要求空間複雜度O(1),所以,這個方法其實並不是最優解。

思路2 一次刪除兩個不同的數

一次刪除兩個不同的數,如果存在majority element,那麼這個majority element一定會最後剩下來,但是,不能說一次刪除兩個不同的數,最後剩下了來的數就是majority element,比如{1,2,3,4,5} 這個數組,最後剩下5,5不是要求的值。所以,在執行完每次刪除兩個不同的數這個操作後,最後留下的數,還要過一遍數組,看下這個數是不是超過了半數,如果超過半數,才算是最後結果。程式碼見:

    public static int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        
        int cand = nums[0];
        int HP = 1;
        int i = 1;
        int limit = nums.length >> 1;
        while (i < nums.length) {
            if (cand == nums[i]) {
                HP++;
                // 如果某時,HP已經大於一半的數了,直接返回
                if (HP > limit) {
                    return nums[i];
                }
            } else {
                if (HP == 0) {
                    cand = nums[i];
                    HP++;
                } else {
                    HP--;
                }
            }
            i++;
        }
        if (HP == 0) {
            return -1;
        }
        int c = 0;
        for (int num : nums) {
            if (cand == num) {
                c++;
            }
        }
        if (c > limit) {
            return cand;
        } else {
            return -1;
        }
    }

說明:
其中HP標識候選數出現的次數,我們可以假設侯選數一開始就是num[0],只要遍歷到的數和候選數一致,HP++,不一致,直接HP歸零,侯選數置為當前數,這樣就實現了一次刪除兩個數的目的。
此外,這裡有一個小的貪心,就是當HP已經到達數組一半以上的大小時候,直接返回當前的候選數(因為HP就表示侯選數出現的次數)

更多

演算法和數據結構筆記

參考資料