【朱迪的LeetCode刷题笔记】169. Majority Element #Easy #Python

Judie

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?

Judy
Python divide and conquer  runtime beats 57.23% memory beats 8.57% taught by cs341

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        h = len(nums) // 2
        
        def f(lst):
            l = len(lst)  
            m = l // 2
            
            if l % 2 == 1 and nums.count(lst[-1]) > h:
                return lst[-1]            
            
            if l == 1:
                return lst[0]

            if l == 2:
                if nums.count(lst[0]) > h:
                    return lst[0]
                return lst[1]

            nlst = []
            
            for i in range(0, m):
                if lst[i] == lst[i+m]:
                    nlst.append(lst[i])
            
            return f(nlst)
        
        return f(nums)

Python boyer more majority vote algorithm runtime beats 65.21% memory beats 67.84% taught by sol

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        x = 0
        c = 0

        for n in nums:
            if c == 0:
                x = n
                c += 1
            elif x == n:
                c += 1
            else:
                c -= 1
        
        return x

Sol1

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = 0;

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