Programming

Leetcode-169. Majority Element

By PattySung 20 August 2023
Leetcode-169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3] Output: 3 Example 2:

Input: nums = [2,2,1,1,1,2,2] Output: 2

<解題>1. sorting


class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return nums[n/2];
    }
}

T: O(n log n)

<解題>2. HashMap


class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        
        n = n / 2;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > n) {
                return entry.getKey();
            }
        }
        
        return 0;
    }
}

Time: O(n) Space: O(n)

<解題>3. Boyer–Moore majority vote algorithm(摩爾投票算法)

  1. 取出第一個數放到一個暫存的變數(res)，將計數器(cnt)設定為1，代表這個數出現1次。
  2. 取出下一個數nums[i]，如果和res相等，則將計數器+1； 如果和res不同，且計數器>0時，將計數器-1；(代表取這兩個數成對移除) 如果和res不同但是計數器=0時，將res更改為nums[i]並將計數器+1 (代表res已經用完了，現在還沒被移除的是nums[i])
  3. 反覆進行步驟2直到陣列結尾，剩下的res即為答案。 (因為兩兩移除到最後一定是非majority element的先被移光)


class Solution {
    public int majorityElement(int[] nums) {
        int ele = 0, vote =0;
        for(int num : nums){
            if(num == ele && vote > 0){
                vote +=1;
            } else if(vote ==0){
                ele = num;
                vote = 1;
            } else {
                vote -=1;
            }
        }
        return ele;
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int res = 0;
        
        for (int num : nums) {
            if (count == 0) {
                res = num;
            }
            
            if (num == res) {
                count++;
            } else {
                count--;
            }
        }
        
        return res;
    }
}

Time: O(nlogn) Space: O(n)

兩種寫法：


for(int i=0; i<nums.length ; i++){
    if(map.containsKey(nums[i])){
        map.put(nums[i], map.get(nums[i]) + 1);
    else{
        map.put(nums[i], 1);
        }
    }

相同


for (int i = 0; i < n; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }