Leetcode4 两个排序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
二分搜索
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m,n = len(nums1),len(nums2)
if (m+n)%2 == 0:
return (self.find_kth(nums1,0,m-1,nums2,0,n-1,(m+n)>>1) + self.find_kth(nums1,0,m-1,nums2,0,n-1,((m+n)>>1)+1))/2
else:
return self.find_kth(nums1,0,m-1,nums2,0,n-1,((m+n)>>1)+1)
def find_kth(self,nums1,b1,e1,nums2,b2,e2,k):
"""
nums1,nums2:两个数组
b1,e1,b2,e2:数组1、2开始和结束的位置
k:第k大
"""
m,n = e1-b1+1, e2-b2+1
if m>n:
return self.find_kth(nums2,b2,e2,nums1,b1,e1,k)
if m==0:
return nums2[b2+k-1]
if k==1:
return min(nums1[b1],nums2[b2])
ia = min(k>>1,m)
ib = k - ia
if nums1[b1+ia-1] < nums2[b2+ib-1]:
return self.find_kth(nums1,b1+ia,e1,nums2,b2,e2,k-ia)
elif nums1[b1+ia-1]>nums2[b2+ib-1]:
return self.find_kth(nums1,b1,e1,nums2,b2+ib,e2,k-ib)
else:
return nums1[b1+ia-1]
Leetcode378 在行和列都是单调递增的数组中找出第k小的元素。
二分搜索1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution:
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
n = len(matrix)
left,right = matrix[0][0],matrix[n-1][n-1]
while left<right:
mid = (left+right)>>1
counts = self.search_less_count(matrix,mid)
if counts <k:
left = mid+1
else:
right = mid
return left
def search_less_count(self,matrix,target):
n = len(matrix)
i,j = n-1,0
counts = 0
while i>=0 and j<n:
if matrix[i][j]<=target:
counts += i+1
j += 1
else:
i -= 1
return counts