⓹➅ Majority Element

Top Interview 150, leetcode Easy, C++, Algorithm

Today’s code

來源

Solution 1 / Time Limit Exceeded

這裡我的設計是先作排序後，在找出最多的，這裡找出的方法是根據提示majority的定義為整個長度超過一半，所以經過排序之後，nums[length / 2] 會是數量最多的元素。

這裡我是用insertion sort排序法，但是回報是程式執行太久。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Insertion sort
        int length = nums.size();
        int start_index = 0;
        int end_index = 0;
        int majority_count = 0;
        for (int j = 1; j < length; j++) {
            for (int i = 0; i < j; i++) {
                if (nums[i] > nums[j]) {
                    start_index = i;
                    end_index = j;
                    int tmp_val = nums[end_index];
                    for (int shift_index = end_index - 1;
                         shift_index >= start_index; shift_index--) {
                        nums[shift_index + 1] = nums[shift_index];
                    }
                    nums[start_index] = tmp_val;
                    break;
                }
            }
        }
        // sort(nums.begin(), nums.end());

        return nums[length / 2];
    }
};

Solution 2 sort()

所以我就改成了sort api去排序（quick sort）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
       int length = nums.size();
        sort(nums.begin(), nums.end());

        return nums[length / 2];
    }
};

Solution 3 Hash Map

此寫法跟之前練習過的利用序號當作值去做記錄很像，這裡我們就用key去存取並將其值紀錄有幾個數字。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // hash map
        int length = nums.size();
        unordered_map <int, int>majorityMap;
        for(int i = 0; i < length; i++){
            majorityMap[nums[i]]++;
        }

        for(auto tmp: majorityMap){
            if(tmp.second > length / 2){
                return tmp.first;
            }
        }
        return 0;
    }
};

Solution 4 moore voting algorithm

moore voting的想法也一個前提是，我們的majority element是超過總元素一半，也就是說假設總元素為n，majority element的數量至少為n/2個。

有了這個前提之後，我們可以額外設計兩個變數：count, current_majority

兩個起始值分別設為：count = 1, current_majority = 第一個元素;

當下一個元素跟我們所存取的元素值一樣時，count++;若不一樣時，則count減一。還記得我們有一個題目的前提就是：current_majority會是總元素數量至少一半。所以，最多的元素一定會會讓他的count大於零。

另外加一個條件，當count等於0時，則會將current_majority改為令他減一的那個元素，也就是與上一個current_majority 不同的元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int length = nums.size();
        int count = 1;
        int current_majority = nums[0];

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

參考

https://leetcode.com/problems/majority-element/solutions/3676530/3-method-s-beats-100-c-java-python-beginner-friendly