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)).
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 这道题给定两个由小到大已排好序的列表，将它继续由从小到大的顺序排列，并返回新列表的中间值。（要求时间复杂度不能超过O(log (m+n))） 首先，给定的两个列表都是已经排好序的，所以我们不使用几种排序算法，他们的时间复杂度都超过了log(m+n)。我们可以使用数据结构中学到的归并(MergeList)两个已排好序的链表的方法。
#-*-coding:utf-8-*- class Node(object):
'''
定义链表的结点
'''
def __init__(self,val):
self.val = val
self.next = None class Solution(object):
def initlist(self,nums):
'''
链表转换函数，传入一个列表，返回列表中元素组成的有头结点的链表
'''
l = Node(0)
ll = l
for num in nums:
node = Node(num)
ll.next = node
ll = ll.next
return l def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
list1 = self.initlist(nums1)
list2 = self.initlist(nums2)
list3 = Node(0)
pa = list1.next
pb = list2.next
pc = list3 while(pa and pb):
if(pa.val<=pb.val):
pc.next = Node(pa.val)
pc = pc.next
pa = pa.next
else:
pc.next = Node(pb.val)
pc = pc.next
pb = pb.next # 插入剩余段
if pa:
pc.next = pa
else:
pc.next = pb # 将已排好序的链表list3转换为列表nums3
nums3 = []
ll = list3.next
while(ll):
nums3.append(ll.val)
ll = ll.next j = len(nums3)/2
if len(nums3)%2==0:
return (nums3[j]+nums3[j-1])/2.0
else:
return nums3[j]