LeetCode算法—分治法

思路：分治法的核心思想是“分而治之”，即将一个复杂的问题分成多个较小的子问题，分别求解这些子问题，然后将子问题的解合并，得到原问题的解。具体到求众数的问题上，分治法通过递归地将数组分成两部分，分别找出每一部分的众数，最后通过合并步骤来确定整个数组的众数。

LeetCode

169多数元素

#方法1 分治递归解决-5.3%
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def majority_element_rec(start, end):
            if start == end:
                return nums[start]
            
            mid = (start + end) // 2
            left_majority = majority_element_rec(start, mid)
            right_majority = majority_element_rec(mid + 1, end)
            
            if left_majority == right_majority:
                return left_majority
            
            return max([left_majority, right_majority], key=nums[start:end + 1].count)
        
        return majority_element_rec(0, len(nums) - 1)
#方法2 哈希表-5.4%
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        hash_map={}
        for i in nums:
            if i in hash_map:
                hash_map[i]+=1
            else:
                hash_map[i]=1

        for key,value in hash_map.items():
            if value>len(nums)/2:
                return key
#方法3 排序-97%（效率最高）
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return int(nums[len(nums)//2])

53 最大数组和

#方法1 动态规划
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 初始化 max_current 和 max_global 为数组的第一个元素
        max_current = max_global = nums[0]
        # 从第二个元素开始遍历
        for num in nums[1:]:
            # 更新当前子数组的最大和
            max_current = max(num, max_current + num)
            # 更新全局最大子数组的和
            max_global = max(max_global, max_current)
        return max_global
 #方法2 分治法-不推荐
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def find_max_subarray(nums, left, right):
            # 基础情况：只有一个元素时
            if left == right:
                return nums[left]
            mid = (left + right) // 2
            # 递归地求左半部分和右半部分的最大子数组和
            left_max = find_max_subarray(nums, left, mid)
            right_max = find_max_subarray(nums, mid + 1, right)
            # 计算跨越中点的最大子数组和
            cross_max = find_cross_max_subarray(nums, left, mid, right)
            # 返回三者中的最大值
            return max(left_max, right_max, cross_max)
        def find_cross_max_subarray(nums, left, mid, right):
            # 从中点向左计算最大子数组和
            left_sum = float('-inf')
            curr_sum = 0
            for i in range(mid, left - 1, -1):
                curr_sum += nums[i]
                left_sum = max(left_sum, curr_sum)
            # 从中点向右计算最大子数组和
            right_sum = float('-inf')
            curr_sum = 0
            for i in range(mid + 1, right + 1):
                curr_sum += nums[i]
                right_sum = max(right_sum, curr_sum)
            # 跨越中点的最大子数组和
            return left_sum + right_sum
        return find_max_subarray(nums, 0, len(nums) - 1)