两个数列的第K大数

简介

本篇笔记主要记录,运用递归求解两个有序数列第K大数问题。

Median of Two Sorted Arrays

题目来源:LeetCode 4

方案一:用merge sort思路排序,排序后取k-1的元素;
方案二:两个指针,分别指向两个序列的开头,逐次比较元素;
方案三:二分剔除

方案三解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def getKth(self, A, B, k):
lenA = len(A); lenB = len(B)
if lenA > lenB: return self.getKth(B, A, k)
if lenA == 0: return B[k - 1]
if k == 1: return min(A[0], B[0])
pa = min(k/2, lenA); pb = k - pa
if A[pa - 1] <= B[pb - 1]:
return self.getKth(A[pa:], B, pb)
else:
return self.getKth(A, B[pb:], pa)
def findMedianSortedArrays(self, A, B):
lenA = len(A); lenB = len(B)
if (lenA + lenB) % 2 == 1:
return self.getKth(A, B, (lenA + lenB)/2 + 1)
else:
return (self.getKth(A, B, (lenA + lenB)/2) + self.getKth(A, B, (lenA + lenB)/2 + 1)) * 0.5

分享