力扣算法打卡刷题|??思维导图整理大厂面试高频数组10: 3种方法彻底解决中位数问题, 力扣4??
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.
想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解 和 其他文章/导图讲解, 更易于理解, 欢迎来看!
题目链接: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
文章目录
- 0.导图整理
- 1.常规思想的改进: 假合并/奇偶合并
- 2.寻找第k小数 代码详解
- 3.理解中位数作用进行 划分数组
- 源码
- Python:
- java:
力扣上对于此题的各种思想的讲解已经非常详细了(图文并茂), 但是他们对于自己的代码几乎没什么补充, 大多都是思想讲解完成直接就上代码了, 但是本题即使思想理解了, 在代码的理解上还是有难度的, 所以本文重点对 代码的理解 做了详细的解释.
0.导图整理
1.常规思想的改进: 假合并/奇偶合并 本题的常规思想还是挺简单的: 使用归并的方式, 合并两个有序数组, 得到一个大的有序数组. 大的有序数组的中间位置的元素, 即为中位数. 但是这种思路的时间复杂度是 O(m+n), 空间复杂度是 O(m+n), 面试的时候, 面试官肯定不会满意这样的答案的.
因此我们必须想办法将算法进行优化, 这里先介绍一种简单的优化方式, 就是 假合并, 即我们并不需要真的合并两个有序数组, 只要找到中位数的位置即可.
它的思想并不复杂, 由于两个数组的长度已知, 因此中位数对应的两个数组的下标之和也是已知的。维护两个指针, 初始时分别指向两个数组的下标0的位置, 每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾,则只需要移动另一个数组的指针）, 直到到达中位数的位置.
通过这种 假合并 的方式, 我们可以成功的将空间复杂度优化到了O(1), 但是对于时间复杂度并没有什么优化. 讲解这个方法的目的并不是为了让大家掌握此方法, 而是为了让大家掌握此方法的一些巧妙的 优化方式.
此方法理解是比较容易的, 但是真正写代码时候还是很有挑战的, 你不仅要考虑奇偶的问题, 更要考虑 一个数组遍历结束后 的各种边界问题, 其实很多困难题就是难在了对于边界的处理上面了.
此方法的一个优化点就是 将奇偶两种情况合并到了一起, 具体思想如下:
文章图片
这种思想是很有必要的, 对于数组来说, 我们经常会遇到奇偶的两种情况处理, 如果想办法将他们合并在一起, 那代码写起来就是非常顺畅和整洁.
另一种合并的思想是: 我们可以在奇数的时候, 在末尾等处添加一个占位符#等, 这样也是可以将奇数合并成偶数的情况的.
此方法的另一个优化点就是 通过在if条件中加入大量的限制条件, 从而实现了对于各种边界问题的处理, 这也是一种很重要的思想.
文章图片
文章图片
此方法的时间复杂度相对于下面两种思想还是太高了, 大家不用特意掌握此方法, 但是这两个优化的思想还是很重要的, 要好好的理解一下.
接下来我们就来详细讲解两个时间复杂度超低的算法代码思想.
2.寻找第k小数 代码详解 关于本题转换为 第k小数 的思想, 就不用纠结怎么想到的了, 大家就安心的理解思想和代码并将它记在脑中就可以了.
其实关于这个算法的思想并不是太难理解, 主要就是根据两个数的三种比较结果, 不断地去除不满足的元素的过程.
文章图片
我认为这个思想最难的点在于 三种特殊情况的处理, 我们能否想到这三种情况, 并将他们完美的融入到代码之中, 我感觉这才是真正的难点所在.
【力扣算法打卡刷题|??思维导图整理大厂面试高频数组10: 3种方法彻底解决中位数问题, 力扣4??】
文章图片
接下来我们来详细解读此思想的代码实现.
最开始对于奇数和偶数的两种情况进行了判断, 其实是可以将两种情况合并的, 只需要在奇数时求两次同样的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= n or A[aStart] < B[bStart]):
right = A[aStart]
aStart += 1
else :
right = B[bStart]
bStart += 1if (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 + 1m, 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, 0while 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 - 1return (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= 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门科目历年真题 思维导图整理
最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
高等数学 中值定理 一张思维导图解决中值定理所有题型
考研思修 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研近代史 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研马原 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研数学课程笔记 考研英语课程笔记 考研英语单词词根词缀记忆 考研政治课程笔记
Python相关技术 知识点 思维导图整理
Numpy常见用法全部OneNote笔记 全部笔记思维导图整理
Pandas常见用法全部OneNote笔记 全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记 全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记 全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记 全部笔记思维导图整理
Java相关技术/ssm框架全部笔记
Spring springmvc Mybatis jsp
科技相关 小米手机
小米 红米 历代手机型号大全 发布时间 发布价格
常见手机品牌的各种系列划分及其特点
历代CPU和GPU的性能情况和常见后缀的含义 思维导图整理
推荐阅读
- Ⅴ爱阅读，亲子互动——打卡第178天
- 画解算法（1.|画解算法：1. 两数之和）
- 2018-3-24
- 日志打卡
- 以读攻“毒”唤新活动曹彦斌打卡第二天
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 泰拳居家打卡十九天