❤️思维导图整理大厂面试高频数组10: 3种方法彻底解决中位数问题, 力扣4❤️

此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.

目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).

关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.

想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解 和 其他文章/导图讲解, 更易于理解, 欢迎来看!

文章目录

• • 0.导图整理
  • 1.常规思想的改进: 假合并/奇偶合并
  • 2.寻找第k小数 代码详解
  • 3.理解中位数作用进行 划分数组
  • 源码
  • • Python:
    • java:

题目链接: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

力扣上对于此题的各种思想的讲解已经非常详细了(图文并茂), 但是他们对于自己的代码几乎没什么补充, 大多都是思想讲解完成直接就上代码了, 但是本题即使思想理解了, 在代码的理解上还是有难度的, 所以本文重点对 代码的理解 做了详细的解释.

0.导图整理

1.常规思想的改进: 假合并/奇偶合并

本题的常规思想还是挺简单的: 使用归并的方式, 合并两个有序数组, 得到一个大的有序数组. 大的有序数组的中间位置的元素, 即为中位数. 但是这种思路的时间复杂度是 O(m+n), 空间复杂度是 O(m+n), 面试的时候, 面试官肯定不会满意这样的答案的.

因此我们必须想办法将算法进行优化, 这里先介绍一种简单的优化方式, 就是 假合并, 即我们并不需要真的合并两个有序数组, 只要找到中位数的位置即可.

它的思想并不复杂, 由于两个数组的长度已知, 因此中位数对应的两个数组的下标之和也是已知的。维护两个指针, 初始时分别指向两个数组的下标0的位置, 每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾,则只需要移动另一个数组的指针）, 直到到达中位数的位置.

通过这种 假合并 的方式, 我们可以成功的将空间复杂度优化到了O(1), 但是对于时间复杂度并没有什么优化. 讲解这个方法的目的并不是为了让大家掌握此方法, 而是为了让大家掌握此方法的一些巧妙的 优化方式.

此方法理解是比较容易的, 但是真正写代码时候还是很有挑战的, 你不仅要考虑奇偶的问题, 更要考虑 一个数组遍历结束后 的各种边界问题, 其实很多困难题就是难在了对于边界的处理上面了.

此方法的一个优化点就是 将奇偶两种情况合并到了一起, 具体思想如下:

这种思想是很有必要的, 对于数组来说, 我们经常会遇到奇偶的两种情况处理, 如果想办法将他们合并在一起, 那代码写起来就是非常顺畅和整洁.

另一种合并的思想是: 我们可以在奇数的时候, 在末尾等处添加一个占位符#等, 这样也是可以将奇数合并成偶数的情况的.

此方法的另一个优化点就是 通过在if条件中加入大量的限制条件, 从而实现了对于各种边界问题的处理, 这也是一种很重要的思想.

此方法的时间复杂度相对于下面两种思想还是太高了, 大家不用特意掌握此方法, 但是这两个优化的思想还是很重要的, 要好好的理解一下.

接下来我们就来详细讲解两个时间复杂度超低的算法代码思想.

2.寻找第k小数 代码详解

关于本题转换为 第k小数 的思想, 就不用纠结怎么想到的了, 大家就安心的理解思想和代码并将它记在脑中就可以了.

其实关于这个算法的思想并不是太难理解, 主要就是根据两个数的三种比较结果, 不断地去除不满足的元素的过程.

我认为这个思想最难的点在于 三种特殊情况的处理, 我们能否想到这三种情况, 并将他们完美的融入到代码之中, 我感觉这才是真正的难点所在.

接下来我们来详细解读此思想的代码实现.

最开始对于奇数和偶数的两种情况进行了判断, 其实是可以将两种情况合并的, 只需要在奇数时求两次同样的k就可以了.

接下来处理了三种特殊情况中的两种特殊情况: 一个数组为空 和 k=1.

下面的几个定义就非常重要了, 一定要弄清这些定义的含义, 才能更轻松的理解代码.

index1, index2作为数组的起始点的下标, 初值都是0, 但是随着两个数组不断被删除元素, 这两个起始点也是在不断的进行变化, 具体变化方式就是 index1 = newIndex1 + 1, 因为在删除元素的时候 连同比较位置也一同删去了, 所以新的开始是 比较位置 的后一位.

newindex1, newindex2作为比较点就是图中被框中的两个数的下标, 它的赋值过程就涉及到了 最后一个边界情况. 因为当一个数组较短时, 其中一个比较点可能已经到达了数组的最后, 所以它的值是 两种情况下较小的那个数.

接下来就是根据两个比较点的大小来进行不同的操作过程了, 这里最难理解的点就是 k -= (newIndex1 - index1 + 1), 也就是减去元素的个数问题了. 我们根据上面的图来举例, 图中index1的值为0, newindex1的值经过计算为1, 通过比较后, 可以看到 红色的数 就是被删除的数, 也就是两个, 所以我们需要在最后+1才是真实被删去的个数. 对于此类问题在确定最终个数的时候, 我们都可以通过这样的特例来决定代码的书写, 至此代码就全部讲解完成了.

3.理解中位数作用进行 划分数组

最后这种思想的时间复杂度甚至比上面的还低, 上面的思想每一轮循环可以将查找范围减少一半,因此时间复杂度是O(log(m+n)), 但这种思想可以对确定的较短的数组进行二分查找, 所以它的时间复杂度是 O(log min(m,n)).

划分数组 正好和上面算法完全相反, 它的思想特别复杂, 但思想理解了, 代码写起来倒是没太大的难度, 所以我们重点说说它的思想.

首先我们要明白中位数的作用: 将一个集合划分为两个长度相等的子集, 其中一个子集中的元素总是大于另一个子集中的元素, 这种思想无论是在几个数组中都是适用的, 这就衍生出了下面的算法思想.

首先来讨论奇偶的两种不同情况下的不同划分方式.

然后在编写代码的时候, 由于计算机的取整操作, 我们是可以将这两种情况合并成一种代码书写方式的. 其中的i和j分别是两个数组的划分位置.

同样我们也会遇到复杂的边界问题, 但下面这种处理方式是真的非常优秀.

上面问题都考虑完了, 其实就可以写代码了, 但是我们需要进行两个条件的判断: B[j−1]≤A[i] 以及A[i−1]≤B[j], 为了优化代码, 经过分析后, 我们发现这两种情况是可以等价转换的. 也就是只需要进行一个条件的判断即可.

代码中有个注意点就是java中的三目运算符? : 在Python中是没有引入这个符号的, 但是Python利用了已有的关键字if…else实现了这个功能.

源码

Python:

# 常规思想class Solution:    def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:        m = len(A)        n = len(B)         lens = m + n        left, right = -1, -1        aStart, bStart = 0, 0        for i in range(lens//2 + 1) :            left = right  # 每次循环前将 right 的值赋给 left            # A移动的条件: B遍历到最后 或 当前A            if aStart < m and (bStart >= n or A[aStart] < B[bStart]):                right = A[aStart]                aStart += 1            else :                right = B[bStart]                bStart += 1                    if (lens & 1) == 0: # 与1交,判断奇偶数,更快速            return (left + right) / 2.0        else:            return right# 第k小数class Solution:    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:        def getKthElement(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 的值,减去删除的数的个数            """                        index1, index2 = 0, 0            while True:                # 特殊情况                if index1 == m:                    return nums2[index2 + k - 1]                if index2 == n:                    return nums1[index1 + k - 1]                if k == 1:                    return min(nums1[index1], nums2[index2])                # 正常情况,index1,index2作为起始点,newindex1,newindex2作为比较点 在不停的更新                newIndex1 = min(index1 + k // 2 - 1, m - 1)  # 第一种特殊情况,发生越界,记录需要比较的位置                newIndex2 = min(index2 + k // 2 - 1, n - 1)  # 第一种特殊情况,发生越界,记录需要比较的位置                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]  # 获取两个需要比较的数                if pivot1 <= pivot2:  # <=将两种情况合并                    k -= newIndex1 - index1 + 1  # 两者相减后+1,这才是真正减去的长度                    index1 = newIndex1 + 1  # 连同比较位置也一同删去了,所以新的开始是 比较位置 的后一位                else:                    k -= newIndex2 - index2 + 1                    index2 = newIndex2 + 1                m, n = len(nums1), len(nums2)        totalLength = m + n        if totalLength % 2 == 1:  # 可以将两种情况合并,奇数会求两次同样的k            return getKthElement((totalLength + 1) // 2)        else:            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2# 划分数组class Solution:    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:        if len(nums1) > len(nums2):            return self.findMedianSortedArrays(nums2, nums1)        infinty = 2**40  # 代表正无穷        m, n = len(nums1), len(nums2)        left, right = 0, m        # median1：前一部分的最大值        # median2：后一部分的最小值        median1, median2 = 0, 0        while left <= right: # 一直循环找到一个最大的i满足A[i−1]≤B[j]            # 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]            # // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]            i = (left + right) // 2            j = (m + n + 1) // 2 - i            # nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]            # 当一个数组不出现在前一部分时,对应的值为负无穷,就不会对前一部分的最大值产生影响            nums_im1 = (-infinty if i == 0 else nums1[i - 1]) # 注意写法与java不同            # 当一个数组不出现在后一部分时,对应的值为正无穷,就不会对后一部分的最小值产生影响            nums_i = (infinty if i == m else nums1[i])            nums_jm1 = (-infinty if j == 0 else nums2[j - 1])            nums_j = (infinty if j == n else nums2[j])            if nums_im1 <= nums_j:                median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)                left = i + 1            else:                right = i - 1        return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1

java:

// 常规思想class Solution {    public double findMedianSortedArrays(int[] A, int[] B) {        int m = A.length;        int n = B.length;        int len = m + n;        int left = -1, right = -1;        int aStart = 0, bStart = 0;        for (int i = 0; i <= len / 2; i++) {            left = right;  // 每次循环前将 right 的值赋给 left            // A移动的条件: B遍历到最后 或 当前A            if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {                right = A[aStart++];            } else {                right = B[bStart++];            }        }        if ((len & 1) == 0) // 与1交,判断奇偶数,更快速            return (left + right) / 2.0;        else            return right;    }}// 第k小数class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        int length1 = nums1.length, length2 = nums2.length;        int totalLength = length1 + length2;        if (totalLength % 2 == 1) {  // 可以将两种情况合并,奇数会求两次同样的k            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) {             // 第三种特殊情况,k=1                return Math.min(nums1[index1], nums2[index2]);            }                        // 正常情况,index1,index2作为起始点,newindex1,newindex2作为比较点 在不停的更新            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); //两者相减后+1,这才是真正减去的长度                index1 = newIndex1 + 1;  //连同比较位置也一同删去了,所以新的开始是 比较位置 的后一位            } else {                k -= (newIndex2 - index2 + 1);                index2 = newIndex2 + 1;            }        }    }}// 划分数组class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        if (nums1.length > nums2.length) {            return findMedianSortedArrays(nums2, nums1);        }        int m = nums1.length;        int n = nums2.length;        int left = 0, right = m;        // median1：前一部分的最大值        // median2：后一部分的最小值        int median1 = 0, median2 = 0;        while (left <= right) { // 一直循环找到一个最大的i满足A[i-1]≤B[j]            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]            int i = (left + right) / 2; //二分法,i从区间中间开始            int j = (m + n + 1) / 2 - i;//+1的操作将总数为奇数和偶数合并为一种情况            //nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]            //当一个数组不出现在前一部分时,对应的值为负无穷,就不会对前一部分的最大值产生影响            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);            //当一个数组不出现在后一部分时,对应的值为正无穷,就不会对后一部分的最小值产生影响            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);            if (nums_im1 <= nums_j) {                median1 = Math.max(nums_im1, nums_jm1);                median2 = Math.min(nums_i, nums_j);                left = i + 1;            }            else {                right = i - 1;            }        }        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;    }}

我的更多精彩文章链接, 欢迎查看

各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)

力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)

计算机专业知识 思维导图整理

最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)

最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目

最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介

最值得收藏的 算法分析与设计 全部知识点思维导图整理(北大慕课课程)

最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理

最值得收藏的 人工智能导论 全部知识点思维导图整理(王万良慕课课程)

最值得收藏的 数值分析 全部知识点思维导图整理(东北大学慕课课程)

最值得收藏的 数字图像处理 全部知识点思维导图整理(武汉大学慕课课程)

红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比

各种常见排序算法的时间/空间复杂度 是否稳定 算法选取的情况 改进 思维导图整理

人工智能课件 算法分析课件 Python课件 数值分析课件 机器学习课件 图像处理课件

考研相关科目 知识点 思维导图整理

考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)

东南大学 软件工程 906 数据结构 C++ 历年真题 思维导图整理

东南大学 软件工程 复试3门科目历年真题 思维导图整理

最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理

最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理

高等数学 中值定理 一