算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做寻找两个正序数组的中位数，这道题很有意思，我们先来看题面：
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.
https://leetcode-cn.com/problems/median-of-two-sorted-arrays
翻译
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
样例
示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
方法一：二分查找
给定两个有序数组，要求找到两个有序数组的中位数，最直观的思路有以下两种：
使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。
不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。
class Solution { 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 - 1, midIndex2 = totalLength / 2; double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0; return median; } } public int getKthElement(int[] nums1, int[] nums2, int k) { /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较 * 这里的 "/" 表示整除 * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个 * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个 * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个 * 这样 pivot 本身最大也只能是第 k-1 小的元素 * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组 * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组 * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 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; } } } }
本题还有第2个方法：划分数组 ，大家有兴趣的自己去leetcode学习一下，今天文章就不说了，这个比较有难度 。
如果喜欢本文，请顺手点个赞或者转发吧。
