0004._median_of_two_sorted_arrays.md

Links:

1. https://leetcode.com/problems/median-of-two-sorted-arrays
2. https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

Tags:

1. 数组
2. 二分查找
3. 分治算法
4. 双指针

Solution1:

前提: works for python3. 因为python2的'/'操作符与python3的'/'操作符不同。例如，3/2，在python2中结果为1，在python3中结果为1.5。

1. 将两个有序列表合并，然后再排序。nums1 + nums2 = nums3。
2. 如果排序后的列表长度为奇数，那么中位数为列表中间的数。
3. 如果排序后的列表长度为偶数，那么中位数为列表中间两个数的平均数。 PS: 这里用了python的sort，这是timesort：

Worst complexity: n*log(n)

Average complexity: n*log(n)

Best complexity: n

Space complexity: n

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        # You may assume nums1 and nums2 cannot be both empty.
        if nums1 is None:
            nums3 = nums2
        if nums2 is None:
            nums3 = nums1
        if nums1 is not None and nums2 is not None:
            nums3 = nums1 + nums2
        nums3.sort()
        length = len(nums3)
        if length % 2 == 1:
            ans = nums3[length // 2]
        else:
            ans = (nums3[(length // 2) - 1] + nums3[length // 2]) / 2     
        return ans

---

class Solution:
    def median(self, nums):
        length = len(nums)
        if length % 2 == 0:
            d = (nums[length // 2] + nums[(length // 2) - 1]) / 2
            return d
        elif length % 2 == 1:
            return nums[length // 2]
        
    def findMedianSortedArrays(self, nums1, nums2):
        if not nums1:
            return self.median(nums2)
        if not nums2:
            return self.median(nums1)
        
        return self.median(sorted(nums1 + nums2))

---

package main

import "sort"

func median(nums []int) float64 {
	length := len(nums)

	if length%2 == 0 {
		return float64(nums[length/2]+nums[(length/2)-1]) / 2
	} else {
		return float64(nums[length/2])
	}
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	if nums1 == nil {
		return median(nums2)
	}

	if nums2 == nil {
		return median(nums1)
	}

	nums3 := append(nums1, nums2...)
	sort.Ints(nums3)
	return median(nums3)
}

Solution2

1. 转化为findKth的问题。
2. nums1设置一个指针，nums2设置一个指针，每次向较小值移动，找到中位数位置（不像Solution1那样合并两个数组）。
3. 但是时间复杂度为O(m + n)

Solution3

1. 比Soultion2更加快。思路也是一样，转成求A和B数组中第k小的数的问题,然后用k/2在A和B中分别找（递归）。时间复杂度为O(log(m + n))。

http://chaoren.is-programmer.com/posts/42890.html