leetcode_4

Posted on | In

[LeetCode: No.4]

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.

仔细分析题目，nums1和nums2都已经是排好序了的，这就大大的降低了难度，让找到两个列表的中间值，其实我们可以拓展为找到两个列表的第k个值。当然这个是拓展部分了，对于这个题目，有不同的思路，最简单粗暴的就是将两个列表合并，之后进行排序，拍好序后进行寻找中间值就简单了。但是用传统的先合并再排序，效率想必会很低~

我们发现对于两个已经有序的列表（从小到大），其实有一个更优的排序方式：从小到大，依次进行列表元素的比较，较小值放到一个新列表中，比如A中该位置的值较小，将其放到新的列表C中，同时将A列表下一个值继续与B中当前位置元素进行比较，以此类推。这样的比较次数就比先合并在排序小很多啦！代码如下：

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
29
30
31
32
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length = len(nums1)+len(nums2)
        #计算总长度
        num = [0]  * length
        
        index, i_1, i_2 = 0
        #当输入两个列表都还存在元素没进行比较的时候，循环进行对比
        #并将较小值放入新列表，同时较小元素的列表和新列表索引加一
        while i_1<len(nums1) and i_2 < len(nums2):
        	if nums1[i_1] >= nums2[i_2]:
        		num[index] = nums2[i_2]
        		i_2 += 1
        	else:
        	    num[index] = nums1[i_1]
        	    i_1 += 1
        	index += 1
        #当存在某一个列表所有元素已经比较完，即排好了序
        #剩下那个列表剩下的值直接放入新列表对应位置即可
        if i_1 == len(nums1)  :   #这里要注意的是， 我们while语句最后都多加了一个1所以这里是==len(nums1)
        	num[index:] = nums2[i_2:]
        else:
        	num[index:] = nums1[i_1:]
        if length % 2 == 0:
        	return float(num[length//2]+num[length//2 - 1])/2
        else:
        	return num[length//2]