本文共 2714 字，大约阅读时间需要 9 分钟。

给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2，目标是找到这两个数组的中位数，并且时间复杂度为 O(log(m + n))。

方法思路

为了高效地找到两个已排序数组的中位数，我们可以利用二分查找的策略，这样可以将问题拆分为更小的子问题，每一步都能将搜索空间减半，从而达到 O(log(m + n)) 的时间复杂度。

具体步骤如下：

这个方法基于分而治之，每一步都能将问题规模减半，从而保证了高效性和时间复杂度符合要求。

代码实现

import java.util.ArrayList;class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        int m = nums1.length;        int n = nums2.length;        int sum = m + n;        // 确定中间位置k（索引从0开始）        int k = sum / 2;        // 初始化两个指针        int i = 0, j = 0;        // 调用二分查找方法确定中位数位置        return findMedianByBinarySearch(nums1, nums2, m, n, k);    }        public int findElement(int[] array, int index, int m) {        // 二分查找在数组中第index位置的元素        int left = 0, right = m - 1;        int pos = -1;        while (left <= right) {            int mid = (left + right) / 2;            if (array[mid] < index) {                left = mid + 1;            } else {                right = mid - 1;                pos = mid;            }        }        return array[pos];    }        public double findMedianByBinarySearch(int[] nums1, int[] nums2, int m, int n, int k) {        int left = 0, right = Math.min(m, n) - 1;        while (left <= right) {            int mid = (left + right) / 2;            int arr1 = 0, arr2 = 0;            if (mid < m) {                arr1 = nums1[mid];            }            if (mid < n) {                arr2 = nums2[mid];            }            if (arr1 <= arr2) {                if (mid >= m) {                    return arr2;                } else if (mid >= n) {                    return arr1;                } else {                    k -= (mid + 1);                    right = mid - 1;                }            } else {                if (mid >= n) {                    return arr1;                } else if (mid >= m) {                    return arr2;                } else {                    k -= (mid + 1);                    left = mid + 1;                }            }        }        // 计算中位数        if (k % 2 == 1) {            int mid = k / 2;            if (mid < m) return nums1[mid];            else return nums2[mid];        } else {            int mid = k / 2;            double average = (nums1[mid] + nums2[mid]) / 2.0;            return average;        }    }}

代码解释

这种方法充分利用了两个数组已经排序的特性，通过分而治之策略，每一步都将问题规模减半，确保了算法的高效性和时间复杂度的低。