鱼C论坛

 找回密码
 立即注册
查看: 1020|回复: 0

[技术交流] 【朱迪的LeetCode刷题笔记】169. Majority Element #Easy #Python

[复制链接]
发表于 2023-6-6 13:26:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
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;
    }
};

2-Figure14.1-1.png


本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 10:38

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表