本文共 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; } }} 这种方法充分利用了两个数组已经排序的特性，通过分而治之策略，每一步都将问题规模减半，确保了算法的高效性和时间复杂度的低。
转载地址：http://degyk.baihongyu.com/