摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.
想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法! 博主同步更新了算法视频讲解, 更易于理解, 不想看文章的 欢迎来看!
关注博主获得题解更新的最新消息!!!
这是最容易想到的方法: 先将数组nums2放进数组nums1的尾部, 然后直接对整个数组进行排序. 实现起来也是非常简单的, 但时间复杂度和空间复杂度都很高, 毕竟用到了排序算法, 建议面试时候千万别写这种题解, 不然可能直接就回去等通知了!
方法一没有利用数组nums1与nums2已经被排序的性质, 为了利用这一性质, 可以使用双指针方法, 将两个数组看作队列, 每次从两个数组头部取出比较小的数字放到结果中, 这时有个注意点: 必须当两个数组的指针都到达尾部时, 算法才算结束, 这点和下面的方法还是有点区别的, 需要注意一下.
最后一个小的注意点就是在python中的语法: nums1[:] = sorted, 它表示对nums1从头到尾切片, 然后进行一一赋值, 相当于进行了深拷贝.
方法二中, 之所以要使用临时数组变量, 是因为如果直接合并到数组nums1中, nums1中的元素可能会在取出之前被覆盖.
观察可知, nums1的后半部分是空的, 可以直接覆盖而不会影响结果, 所以可以将指针设置为从后向前遍历, 每次取两者之中的较大者放进nums1的最后面, 这样就完美的解决了被覆盖的问题. 下面是合理性的证明, 感兴趣的可以看一下.
严格来说，在此遍历过程中的任意一个时刻，nums1数组中有m−p1−1个元素被放入nums1的后半部，nums2数组中有n−p2−1个元素被放入nums1的后半部，而在指针p1的后面，nums1数组有m+n−p1−1个位置。由于m+n−p1 −1≥m−p1 −1+n−p2 −1 等价于 p2≥−1永远成立，因此p1后面的位置永远足够容纳被插入的元素，不会产生p1的元素被覆盖的情况最后有个注意点, 之前我们说到方法二终止的条件是: 两个指针都遍历到了数组结尾, 但是在这种方法中, 并不需要两个指针都遍历到开头, 只需要nums2空了, 遍历就结束了, 不用考虑nums1, 因为此时nums1中剩下的元素都是小于nums2的最小元素的, 且它们的顺序本来就是排好的, 所以在代码上相较于方法二有了一些简化的操作. 具体可以看两者代码的不同.
这是在面试中可能会被问到的进阶问题, 解决的方法是: 在方法三的基础上, 因为是有序的, 每次比较完两个值后判断前一个放进数组里的值是不是和这次将要放进数组的值相等就行了, 如果相等的话这一步比较出来的值就不放进数组.
但其实这样还是有点问题的: 如果是从大往小排, 如果边排边丢, 可能最后排好的部分全在nums1的后面, 仍然需要遍历一次, 把所有数挪回左边. 如果排完再丢, 也是遍历一次, 感觉没啥区别.
所以这两种方式, 先排再丢 和 边排边丢 似乎是没有区别的, 大家可以自己思考一下, 有问题欢迎留言评论.
# 直接合并后排序class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: nums1[m:] = nums2 nums1.sort()# 常规双指针class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: sorted = [] p1, p2 = 0, 0 while p1 < m or p2 < n: # 同时到达尾部才结束 if p1 == m: sorted.append(nums2[p2]) p2 += 1 elif p2 == n: sorted.append(nums1[p1]) p1 += 1 elif nums1[p1] < nums2[p2]: sorted.append(nums1[p1]) p1 += 1 else: sorted.append(nums2[p2]) p2 += 1 nums1[:] = sorted # 对nums1从头到尾切片, 相当于进行了深拷贝# 逆向双指针class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: p1, p2 = m - 1, n - 1 tail = len(nums1) - 1 while p2 >= 0: if p1 < 0 or nums1[p1] <= nums2[p2]: nums1[tail] = nums2[p2] p2 -= 1 tail -= 1 else: nums1[tail] = nums1[p1] p1 -= 1 tail -= 1// 直接合并后排序class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { for (int i = 0; i != n; ++i) { nums1[m + i] = nums2[i]; } Arrays.sort(nums1); }}// 常规双指针class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = 0, p2 = 0; int[] sorted = new int[m + n]; int cur; while (p1 < m || p2 < n) { // 同时到达尾部才结束 if (p1 == m) { cur = nums2[p2++]; } else if (p2 == n) { cur = nums1[p1++]; } else if (nums1[p1] < nums2[p2]) { cur = nums1[p1++]; } else { cur = nums2[p2++]; } sorted[p1 + p2 - 1] = cur; } for (int i = 0; i != m + n; ++i) { nums1[i] = sorted[i]; } }}// 逆向双指针class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int tail = nums1.length - 1; int p1 = m - 1; int p2 = n - 1; while (p2 >= 0) { // 只要p2到达开头就结束 if (p1 < 0 || nums1[p1] <= nums2[p2]) { nums1[tail--] = nums2[p2--]; } else { nums1[tail--] = nums1[p1--]; } } }}我的更多精彩文章链接, 欢迎查看
各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)
力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)
计算机专业知识 思维导图整理
最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)
最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目
最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介
最值得收藏的 算法分析与设计 全部知识点思维导图整理(北大慕课课程)
最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理
最值得收藏的 人工智能导论 全部知识点思维导图整理(王万良慕课课程)
最值得收藏的 数值分析 全部知识点思维导图整理(东北大学慕课课程)
最值得收藏的 数字图像处理 全部知识点思维导图整理(武汉大学慕课课程)
红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比
各种常见排序算法的时间/空间复杂度 是否稳定 算法选取的情况 改进 思维导图整理
人工智能课件 算法分析课件 Python课件 数值分析课件 机器学习课件 图像处理课件
考研相关科目 知识点 思维导图整理
考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)
东南大学 软件工程 906 数据结构 C++ 历年真题 思维导图整理
最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
考研思修 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研近代史 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研马原 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研数学课程笔记 考研英语课程笔记 考研英语单词词根词缀记忆 考研政治课程笔记
Python相关技术 知识点 思维导图整理
Numpy常见用法全部OneNote笔记 全部笔记思维导图整理
Pandas常见用法全部OneNote笔记 全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记 全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记 全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记 全部笔记思维导图整理
Java相关技术/ssm框架全部笔记
科技相关 小米手机
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123624.html
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
阅读 808·2021-11-22 11:59
阅读 3193·2021-11-17 09:33
阅读 2288·2021-09-29 09:34
阅读 1920·2021-09-22 15:25
阅读 1908·2019-08-30 15:55
阅读 1303·2019-08-30 15:55
阅读 513·2019-08-30 15:53
阅读 3321·2019-08-29 13:55
