[Java知识库] ??思维导图整理大厂面试高频数组10: 3种方法彻底解决中位数问题力扣4??

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> Java知识库 -> ??思维导图整理大厂面试高频数组10: 3种方法彻底解决中位数问题力扣4?? -> 正文阅读

[Java知识库]??思维导图整理大厂面试高频数组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<B,满足一个即可
            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<B,满足一个即可
            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;
    }
}