Majority Element - LeetCode

https://leetcode.com/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150

LeetCode_Sharing.png

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

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • 109 <= nums[i] <= 109

Follow-up: Could you solve the problem in linear time and in O(1) space?

解析

最笨的方法来了。时间上居然也打败了44.45% ，看来笨办法还是很多的，比如unique一下，挨个循环找数量，但是这种方法显然是不好的，unique和sort这样的高级方法并不是很好。但好歹能解决问题，太tricky的方法不好想。值的注意的地方是，很多边界限制问题需要提前考虑。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        nums.sort()
        cnt = 1
        flag = nums[0]
        n = (len(nums) / 2) if len(nums) % 2 == 0 else (len(nums) + 1) / 2
        for i in range(1, len(nums)):
            if flag == nums[i]:
                cnt += 1
            else:
                cnt = 0
                flag = nums[i]
                cnt += 1
            if cnt >= n:
                return flag

其他的方法使用的是多数投票算法，Boyer–Moore majority vote algorithm。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = 0
        flag = nums[0]
        for i in range(len(nums)):
            if flag == nums[i]:
                cnt += 1
            else:
                cnt -= 1
                if cnt == 0:
                    flag = nums[i]
                    cnt = 1

        return flag

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

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int flag = nums[0];
        int cnt = 0;
        for (int num : nums) {
            if (num == flag){
                cnt++;
            } else{
                cnt--;
                if (cnt == 0){
                    flag = num;
                    cnt = 1;
                }
            }
        }
        return flag;
    }
};

这个算法的核心内容理解可以类比投票且超过半数当选。循环所有元素，当前投票多的数和循环到的数相同，计数加一，否则减一，当计数器为0，更改当前值为多数。因为guarantee了一定有超过半数的，所以不用验证。