Leetcode_4 Median of Two Sorted Arrays

Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

Tips

For a sorted number a of length n, if n is an odd number, the median is a[n / 2 + 1]. If n is even, the median (a[n / 2] + a[n / 2 + 1]) / 2.
If we can find the Kth element in the two series, we can solve the problem.
It may be desirable to set the number of A elements in the series to be n, and the number of elements in the series B to be m, and sort them in ascending order, and find the kth small element.
Take A[k / 2] B[k / 2] comparison,If A[k / 2] > B[k / 2] then the element sought is inevitably not in the first k / 2 elements of B (proving counter-evidence)
On the contrary, it must not be in the first k / 2 elements of A, so we can delete the first k / 2 elements of the A or B series, and find the remaining two series k - k / 2 small elements, so I got the same problem with the data size becoming smaller. If k / 2 is greater than a certain number of columns, the element sought must not be in the first k / 2 elements of the other series , recursively solved.

Solution2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""

c=nums1+nums2
c=sorted(c)
n=len(c)
a=int((n-1)/2)
if n%2==0:
return (c[a]+c[a+1])/2
else:
return c[a]

Tips

In python, the time complexity of the function len is O(1). The time complexity of the function sort is O(nlog(n)). Timsort algorithm is used for sorted in python.
image
So solution2 actually runs faster than solution1.

-------------End of the articleThank you for reading-------------
  • Author of this article:zfish
  • Link to this article: archives/5599f08d.html
  • Copyright Notice: All articles in this blog, except for special statements, please indicate the source!
0%