《力扣每日一题》—— 合并两个有序数组

本是古典何须时尚 2024-04-23 15:38 65阅读 0赞

> ✅作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
> 
> ?博客首页：[是小鱼儿哈][Link 1]
> 
> ?系列专栏：[一起刷好题][Link 2]
> 
> ?每日一句**：努力不是重点，常态化才是关键。真正努力的人，能随时进入任何角色，在过程中找到感觉和快乐。**
> 
> ?博主也在学习阶段，如发现问题请告知，非常感谢?

![1ccda504d09b47439d0ac2c52e2939e5.png][]

## **?思路一：常规双指针** ##

> **不是说nums1的数组长度是m+n吗？**
> 
> **所以一开始我是想直接把nums2的元素按大小添加到nums1中?**
> 
> **但在添加过程我发现如果直接将nums1和nums2中元素的值进行比较，按大小顺序添加到nums1里，这样是会把原来nums1中的元素 给覆盖掉的，所以我就直接把nums1中合并前的元素复制到了tmp数组中**

> **然后设置两个双指针，分别指向各种数组的起始位置，通过这两个双指针不断的对tmp数组和nums2数组进行大小比较，再依次放到nums1数组中**

**?代码如下：**

>     class Solution {
>         public void merge(int[] nums1, int m, int[] nums2, int n) {
>             int[] tmp = new int[m]; 
>             for (int i = 0; i < m; ++i) tmp[i] = nums1[i]; // 将nums1合并前的元素复制到tmp数组中
>             int p = 0, q = 0, k = 0;
>             while ( p < m && q < n) {
>                 if (tmp[p] <= nums2[q]) { // 如果tmp[p]小，先把tmp[p]放到nums1中
>                     nums1[k] = tmp[p];
>                     ++k; ++p; 
>                 }
>                 else {
>                     nums1[k] = nums2[q];
>                     ++k; ++q;
>                 }
>             }
>             while (p < m) {  // 当nums2中的数组合并完了，直接把tmp数组中剩下的元素依次放到nums1就行
>                 nums1[k] = tmp[p];
>                 ++k; ++p;
>             }
>             while (q < n) {
>                 nums1[k] = nums2[q];
>                 ++k; ++q;
>             }
>         }
>     }

--------------------

## **?思路二：逆序双指针** ##

我们上面那种思路为了防止nums1中的元素被覆盖，用到了额外的数组

?但分析题目后我们发现：**nums1后边都是0，如果我们把比较后的元素放到nums1的后边，也就是把元素从后往前的放到nums1中（这样不就避免了元素覆盖吗?）**

> ?同时我们也应该注意到，既然是把元素从后往前的放到nums1中，那么我们一开始找到肯定这两个数组中最大的元素
> 
> **?所以说我们的两个指针，一开始就应该就应该从各种数组中有效元素的结尾出发，然后让他们两两的进行比较求得较大的那**个。
> 
> ?之后大的继续前移，小的不动，之后再和大的那个元素的前一个进行比较

**代码：**

>     class Solution {
>         public void merge(int[] nums1, int m, int[] nums2, int n) {
>             // 两个指针分别从各自数组的最末尾的一个有效元素出发
>             int i = m - 1, j = n - 1, k = n + m - 1; // 从后往前遍历这样nums1的元素不会被覆盖
>             while (i >= 0 && j >= 0) {
>                 if (nums1[i] > nums2[j]) {
>                     nums1[k] = nums1[i];
>                     --i; --k;
>                 }
>                 else {
>                     nums1[k] = nums2[j];
>                     --j; --k;
>                 }
>             }
>             // 如果此时i 还大于0,不用管，因为本来就是把数组合并到nums1中，只用考虑j就行
>             while (j >= 0) {
>                 nums1[k] = nums2[j];
>                 --j; --k;
>             }
>         }
>     }

[Link 1]: https://blog.csdn.net/weixin_61061381?type=blog
[Link 2]: https://blog.csdn.net/weixin_61061381/category_11776133.html
[1ccda504d09b47439d0ac2c52e2939e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2f25b0feefab4e2fb01b8589ec18fd34.png

发表评论取消回复

表情：

评论列表（有 0 条评论，65人围观）

还没有评论，来说两句吧...

相关阅读

相关《力扣每日一题》—— 合并两个有序数组

力扣链表题目——合并两个有序数组

本是古典何须时尚/ 2024年04月23日 15:38/ 0 赞/ 66 阅读

相关力扣：21. 合并两个有序链表

[21. 合并两个有序链表 ][21. _] ![在这里插入图片描述][e6b3c944faac4c82a020df22f76ed5f5.png] /

- 日理万妓/ 2024年03月25日 14:08/ 0 赞/ 78 阅读

相关力扣每日一题：两数之和 II - 输入有序数组

> 给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 n

àì夳堔傛蜴生んèń/ 2024年03月17日 17:03/ 0 赞/ 39 阅读

相关力扣——合并两个有序数组

[合并两个有序数组][Link 1] > 给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 num

秒速五厘米/ 2023年10月02日 11:57/ 0 赞/ 3 阅读

相关合并两个有序数组-力扣88（数组+逆向+双指针+c）

题目描述：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。初始化 nums1 和 nu

分手后的思念是犯贱/ 2023年01月13日 09:22/ 0 赞/ 126 阅读

相关力扣 21. 合并两个有序链表 JavaScript

代码如下 -------------------- //Definition for singly-linked list. function ListNo

短命女/ 2022年11月07日 14:50/ 0 赞/ 140 阅读

相关（力扣）第88. 合并两个有序数组

88. 合并两个有序数组 -------------------- 题目要求：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nu

喜欢ヅ旅行/ 2022年10月22日 07:39/ 0 赞/ 152 阅读

相关力扣合并两个有序数组

88. 合并两个有序数组给你两个按非递减顺序排列的整数数组 `nums1`和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `n

「爱情、让人受尽委屈。」/ 2022年09月14日 00:18/ 0 赞/ 140 阅读

相关力扣 (LeetCode)-合并两个有序数组,字典,散列表

Github来源：力扣 (LeetCode)｜刷题打卡 | 求星星 ✨ | 给个❤️关注，❤️点赞，❤️鼓励一下作者 > \[已开启\]任务一：刷题打卡 \ 10 篇哪吒

超、凢脫俗/ 2021年07月24日 17:43/ 0 赞/ 332 阅读

相关精选力扣500题第22题 LeetCode 88. 合并两个有序数组【c++详细题解】

目录 1、题目 2、思路1 3、代码1 4、思路2

客官°小女子只卖身不卖艺/ 2021年07月24日 15:52/ 0 赞/ 431 阅读