最近再刷leetcode,除了链表之外的都用python 实现,贴出一些代码,希望指正.
问题描述:
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)).
找两个排序好的数组的中位数.
样例输入:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
算法思想:
我再这里对两个数组的len和是奇数还是偶数做了分开对待.
- 如果两个数组len和是奇数.
对两个数组进行从小到大遍历,同时遍历,当遍历到(length+1)/2输出结果,不过需要注意的是,两个数组的长度不同,可能出现某个遍历完了,某个还没有完的情况,所以在同时遍历完成之后还需要,对没有完成的进行遍历. - 对于两个数组的len和是偶数的情况.
如果两个数组的len和是偶数,那就说明中位数,是最中间两个和的一半,这时就需要对上一个结果进行存储,遍历时,需要找到(length+1)//2的下一个然后和上一个加和求二分之一.
代码写的比较臭
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m = len(nums1)
n = len(nums2)
median = (m + n + 1) / 2
# print(median)
def find_int(nums1, nums2, tar):
# print("find_int")
# print(nums1, nums2, tar)
flag = 0
tmp = -1
M = N = 0
while m > M and n > N:
if flag == tar:
return tmp
if nums1[M] < nums2[N]:
tmp = nums1[M]
M = M + 1
flag = flag + 1
else:
tmp = nums2[N]
N = N + 1
flag = flag + 1
while m > M:
if flag == tar:
return tmp
tmp = nums1[M]
M = M + 1
flag = flag + 1
while n > N:
if flag == tar:
return tmp
tmp = nums2[N]
N = N + 1
flag = flag + 1
return tmp
def find_float(nums1, nums2, tar):
# print("find_float")
# print(nums1, nums2, tar)
list_new = []
flag = 0
tmp = -1
M = N = 0
while m > M and n > N:
if flag == tar + 1:
return list_new[-2], tmp
if nums1[M] < nums2[N]:
tmp = nums1[M]
list_new.append(tmp)
M = M + 1
flag = flag + 1
else:
tmp = nums2[N]
list_new.append(tmp)
N = N + 1
flag = flag + 1
while m > M:
if flag == tar + 1:
return list_new[-2], tmp
tmp = nums1[M]
list_new.append(tmp)
M = M + 1
flag = flag + 1
while n > N:
if flag == tar + 1:
return list_new[-2], tmp
tmp = nums2[N]
list_new.append(tmp)
N = N + 1
flag = flag + 1
if flag == tar + 1:
print(list_new)
return list_new[-2], tmp
if (m + n + 1) % 2 == 0:
return find_int(nums1, nums2, int(median))
else:
a, b = (find_float(nums1, nums2, int(median)))
return (a + b) / 2
solution = Solution()
nums1 = [1,1,3,3]
nums2 = [1,1,3,3]
print(solution.findMedianSortedArrays(nums1, nums2))
