Leetcode No.4 Median of Two Sorted Arrays

原题：

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))..

题目大意：给出两个有序的数字列表，长度分别为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

Reference solution

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

我们发现对于两个已经有序的列表（从小到大），其实有一个更优的排序方式：从小到大，依次进行列表元素的比较（为方便表述，小詹称两个列表为A，B），较小值放到一个新列表中，比如A中该位置的值较小，将其放到新的列表C中，同时将A列表下一个值继续与B中当前位置元素进行比较，以此类推。

这样的比较次数就比先合并在排序小很多啦！代码如下：

def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        #创建新列表，并将所有元素初始为0
        nums3 = [0] * (len(nums1)+len(nums2))
        #指定三个列表的索引，初始值为0
        l_i,r_i,i = 0,0,0
        #当输入两个列表都还存在元素没进行比较的时候，循环进行对比
        #并将较小值放入新列表，同时较小元素的列表和新列表索引加一
        while(l_i < len(nums1)) and (r_i < len(nums2)):
            if nums1[l_i] < nums2[r_i]:
                nums3[i] = nums1[l_i]
                l_i += 1
            else:
                nums3[i] = nums2[r_i]
                r_i += 1
            i += 1
        #当存在某一个列表所有元素已经比较完，即拍好了序
        #剩下那个列表剩下的值直接放入新列表对应位置即可
        if l_i != len(nums1):
            nums3[i:] = nums1[l_i:]
        else:
            nums3[i:] = nums2[r_i:]
        #注意‘/’和‘//’的区别
        #前者结果为float类型，后者为整除，结果为int型
        len_3 = len(nums3)
        #‘%’为取模运算，即看长度是否被2整除，即看偶数还是奇数
        if len_3 %2 != 0:
            return float(nums3[(len_3-1)//2])
        return (nums3[len_3//2 - 1]+nums3[len_3//2])/2

My solution

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        # total = [0] * (len(nums1) + len(nums2))
        total = []
        # count = len(total)

#       冒泡排序法
#         for i in range(0, count):
#             for j in range(i + 1, count):
#                 if total[i] > total[j]:
#                     total[i], total[j] = total[j], total[i]

        # # 选择排序
        # for i in range(0, count):
        #     min_index = i
        #     for j in range(i, count):
        #         if total[j] < total[min_index]:
        #             min_index = j
        #     total[min_index], total[i] = total[i], total[min_index]

        # # 插入排序
        # for i in range(1, count):
        #     key = i - 1
        #     mark = total[i]
        #     while key >= 0 and total[key] > mark:
        #         total[key + 1] = total[key]
        #         key -= 1
        #     total[key+1] = mark

#         # shell排序
        # gap = round(count / 2)    # 双杠用于整除（向下取整），在python直接用 “/” 得到的永远是浮点数
        # while gap >= 1:
        #     for i in range(gap, count):
        #         temp = total[i]
        #         j = i
        #         temp_two = total[j - gap]
        #         while j - gap >= 0 and total[j-gap] > temp:
        #             total[j] = total[j-gap]
        #             j -= gap
        #         total[j] = temp
        #     gap = round(gap / 2)

#         # 归并排序

#         total = self.merge_sort(total)

        # # 快速排序
        # total = self.quick_sort(total, 0, count-1)


        len_num1 = len(nums1)
        len_num2 = len(nums2)
        i = j = 0

        while i <= len_num1 -1 and j <= len_num2 - 1:
            if nums1[i] <= nums2[j]:
                total.append(nums1[i])
                i += 1
            else:
                total.append(nums2[j])
                j += 1

        if i == len_num1:
            total += nums2[j:]
        else:
            total += nums1[i:]
        count = len(total)


        if (count % 2) == 0:
            median = (total[int(count/2)] + total[int(count/2)-1]) / 2
        else:
            median = total[int(count/2)]
        return median

    # 归并排序
    def merge_sort(self, ary):

        if len(ary) <= 1:
            return ary

        median = int(len(ary)/2)
        left = self.merge_sort(ary[:median])
        right = self.merge_sort(ary[median:])
        return self.merge(left, right)

    def merge(self, left, right):
        res = []
        i = j = k = 0
        while(i < len(left) and j < len(right)):
            if left[i] < right[j]:
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                j += 1

        res = res + left[i:] + right[j:]
        return res


    def quick_sort(self, total, start, end):

        # 快速排序
        if start < end:
            left = start
            right = end
            key = total[start]
            while (left < right):
                while (left < right) and total[right] >= key:
                    right -= 1
                if left < right:    # 说明上述while循环打破原因是total[right] <= key
                    total[left] = total[right]
                    left += 1
                while left < right and total[left] < key:
                    left += 1
                if left < right:
                    total[right] = total[left]
                    right -= 1
            total[left] = key

            self.quick_sort(total, start, left - 1)
            self.quick_sort(total, left + 1, end)
        return total

上述代码中注销掉的代码是在这个过程实验过的排序算法，可以用，只是为了重新复习排序，又将各大排序算法重新实现了一边，；事实上，只有bubble sort与select sort没能通过时间复杂度，其他算法均能通过只是性能一般。