分治算法例题
leetcode 23
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
n = len(lists)
#注意3 右端点的取值
return self.merge(0,n-1,lists)
def merge(self,l,r,lists):
#注意1 退出条件
if l==r:
return lists[l]
mid = (r-l)//2+l
#注意2 左右端点的取值
left = self.merge(l,mid,lists)
right = self.merge(mid+1,r,lists)
return self.merge_two(left,right)
# 比较函数的书写
def merge_two(self,l,r):
if not l: return r
if not r : return l
if l.val<r.val:
l.next = self.merge_two(l.next,r)
return l
else:
r.next = self.merge_two(l,r.next)
return r
leetcode 169
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
def majority(l,r):
#注意1 退出条件
if l==r:
return nums[l]
mid = (r-l)//2+l
#注意2 左右端点的取值
left = majority(l,mid)
right = majority(mid+1,r)
if left == right:
return left
#注意3 range的取值
left_count = sum(1 for i in range(l,r+1) if nums[i] == left)
right_count = sum(1 for i in range(l,r+1) if nums[i] == right)
return left if left_count>=right_count else right
#注意4 右端点的取值
return majority(0,len(nums)-1)
