点击 这里 能够查看更多算法面试相干内容~

题目形容

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个工夫复杂度为 $O(log (m+n))$ 的算法解决此问题吗？

示例 1：

输出：nums1 = [1,3], nums2 = [2] 输入：2.00000

解释：合并数组 = [1,2,3]，中位数 2

示例 2：

输出：nums1 = [1,2], nums2 = [3,4] 输入：2.50000

解释：合并数组 = [1,2,3,4]，中位数 (2 + 3) / 2 = 2.5

示例 3：

输出：nums1 = [0,0], nums2 = [0,0] 输入：0.00000

示例 4：

输出：nums1 = [], nums2 = [1] 输入：1.00000

示例 5：

输出：nums1 = [2], nums2 = [] 输入：2.00000

提醒：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

奢侈解法

如果疏忽进阶的 $O(log(m + n))$ 要求，这道题就非常简单。

一个比拟直观的做法：将两个数组合并，排序，而后别离获得 total / 2 和 (total - 1) / 2 两个地位的数，取两者平均值。

这样做的目标是为了防止分状况探讨：合并后的数组长度是奇数还是偶数。

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[] arr = new int[n + m];
        int idx = 0;
        for (int i : nums1) arr[idx++] = i;
        for (int i : nums2) arr[idx++] = i;
        Arrays.sort(arr);
        int l = arr[(n + m) / 2], r = arr[(n + m - 1) / 2];
        return (l + r) / 2.0;
    }
}

工夫复杂度：合并两个数组的复杂度是 $O(m + n)$，对合并数组进行排序的复杂度是 $O((m + n)log(m + n))$。整体复杂度是 $O((m + n)log(m + n))$

空间复杂度：$O(1)$

留神：Arrays.sort() 不只有双轴快排实现，这里的复杂度剖析是假设其应用双轴快排。

分治解法

首先能够将原问题等效为：从两个有序数组中找第 k 小的数。

分两种状况探讨：

1. 总个数为偶数：找到 第 (total / 2) 个小的数 和 第 (total / 2 + 1) 个小的数，后果为两者的平均值。
2. 总个数为奇数：后果为 第 (total / 2 + 1) 个小的数。

具体思路为：

• 默认第一个数组比第二个数组的无效长度短，如果不满足，则调换两个数组（这也是一个罕用技巧，目标是缩小边界解决工作：本来须要对两个数组做越界查看，当初只须要对短的数组做越界查看）
• 第一个数组的无效长度从 i 开始，第二个数组的无效长度从 j 开始，其中 [i,si - 1] 是第一个数组的前 k / 2 个元素，[j,sj - 1] 是第二个数组的前 k - k / 2 个元素（为了确保 k 为奇数的时候正确）
• 当 nums1[si - 1] > nums2[sj - 1]：则示意第 k 小肯定不在 [j,sj - 1] 中，即在 [i,n] 或 [sj,m] 中
• 当 nums1[si - 1] <= nums2[sj - 1]：则示意第 k 小肯定不在 [i,si - 1] 中，即在 [si,n] 或 [j,m] 中

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int tot = nums1.length + nums2.length;
        if (tot % 2 == 0) {int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }
    int find(int[] n1, int i, int[] n2, int j, int k) {if (n1.length - i > n2.length - j) return find(n2, j, n1, i, k);
        if (i >= n1.length) return n2[j + k - 1];
        if (k == 1) {return Math.min(n1[i], n2[j]);
        } else {int si = Math.min(i + (k / 2), n1.length), sj = j + k - (k / 2);
            if (n1[si - 1] > n2[sj - 1]) {return find(n1, i, n2, sj, k - (sj - j));
            } else {return find(n1, si, n2, j, k - (si - i));
            }
        }
    }
}

工夫复杂度：每次递归 k 的规模都缩小一半，复杂度为 $O(log(m + n))$

空间复杂度：$O(1)$

总结

明天这道题，我给你介绍了两种技巧：

1. 在机试或者周赛中，目标是尽可能快的 AC，所以 Java 能够间接不写 private 的修饰符（不写代表应用默认的包权限），这没有问题，不必纠结
2. 在机试或者周赛中，遇到一些是从文字上限度咱们的题目，例如本题限度咱们应用 O(log (m+n)) 算法。能够剖析是否可能不依照限度要求来做，具体分析思路为：

   2.1 先有一个很容易实现的算法思路。例如本题很容易就想到间接应用双指针找第 k 个小的数，复杂度为 O(n)。

   2.2 看题目的数据规模①是否撑持咱们应用限度以外的算法。例如本题数据规模只有 1000 + 1000 = 2000。

   2.3 依据数据规模，判断咱们的奢侈算法计算机是否能够在 1s 内解决完②，即判断运算次数是否在 10^7 以内③。例如本题应用双指针算法，指针挪动和判断大小算一次运行，因为数据只有 2000，间隔 10^7 还很远，所以齐全足够了

阐明 ①：正规的算法题目都会提供数据规模，LeetCode 上一些旧题目没有提供，是因为过后出的时候不太标准，LeetCode 新题、其余 OJ 平台题目，算法比赛题目都会有。

阐明 ②：即便是最严格的 OJ 中最简略的题目，也会提供 1s 的运行工夫，超过这个工夫才算超时。

阐明 ③：计算器 1s 内极限的处理速度是 10^8，但为了尽可能不呈现谬误提交，应用技巧时尽量和 10^7 进行比拟。

留神：这两个技巧，我只举荐在机试或者周赛（尽可能快 AC 的场景）中应用。平时练习或者和面试的时候必须诚实依照题目要求来。

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.4 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

因为 LeetCode 的题目随着周赛 & 双周赛一直减少，为了不便咱们统计进度，咱们将依照系列起始时的总题数作为分母，实现的题目作为分子，进行进度计算。以后进度为 4/1916。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：Github 地址 & Gitee 地址。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其余的优选题解。

算法与数据结构

LeetCode 题解

算法面试