题目

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.

---

Example1

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example2

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题目大意

给定两个大小为m和n的有序数组nums1和nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m+n))。
你可以假设nums1和nums2不会同时为空。

解题思路

方法一: 二分查找

这一题所用的思想是二分法，才能让我们最后实现的时间复杂度为log,所以我们需要从二分查找去考虑这个问题。具体的解题思路，可以去看看LeetCode官方给的很仔细的解释
寻找两个有序数组的中位数

代码

package leetcode;

public class D04_FindMedianSortedArrays {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2, midIndex2 = totalLength / 2 - 1;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    private int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            //边界情况
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            //正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }

}

复杂度分析

* 时间复杂度：O(log(m+n)),其中m和n分别是数组nums1和nums2的长度。初始化有 k=(m+n)/2 或 k=(m+n)/2+1, 每一轮循环可以将查找范围减少一半，因此时间复杂度是O(log(m+n))。
* 空间复杂度：O(1)。

方法二: 划分数组

这个算法有点难度，所以留下以后来继续深究。