使用双指针合并两个有序数组

青旅半醒 2022-12-28 11:22 74阅读 0赞

### 题目描述： ###

给定两个有序数组nums1和nums2，请你将nums2合并到nums1中，使nums1成为一个有序数组。

### 说明： ###

*  初始化nums1和nums2的元素数量分别为m和n
 *  假设nums1有足够的空间（空间大小大于或等于m+n）来保存nums2中的元素

### 算法思路： ###

一般而言，对于有序数组可以通过双指针法达到O(n+m)的时间复杂度

最直接的算法实现是将指针p1置为nums1的开头，p2为nums2的开头，在每一步将最小值放入输出数组中。由于nums1是用于输出的数组，需要将nums1中的前m个元素放在其他地方，也就需要O(m)的空间复杂度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpX3dfY2g_size_16_color_FFFFFF_t_70][]

### 算法java实现： ###

class Solution {
        public void merge(int [] nums1, int m, int[] nums2, int n) {
            //赋值nums1
            int[] nums1_copy = new int[m];
            System.arraycopy(nums1, 0, nums1_copy, 0, m);
            
            //nums1_copy的指针
            int p1 = 0;
            //nums2的指针
            int p2 = 0;
            //nums1的指针
            int p = 0;
            
            //比较nums1_copy和nums2，直到较小的一个完全添加到nums1中
            while ((p1 < m) && (p2 < n))
                nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
    
            //插入剩余元素,直接复制
            if (p1 < m)
                System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m+n-p1-p2);
            if (p2 < n)
                System.arraycopy(nums2, p2, nums1, p1 + p2, m+n-p1-p2);
        }
    }

*  [System.arraycopy()方法剖析 ][System.arraycopy_]

### 复杂度分析： ###

*  时间复杂度：O(n+m)
 *  空间复杂度：O(m)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpX3dfY2g_size_16_color_FFFFFF_t_70]: /images/20221120/18ffc09aadf84f51b0d9d4311f0003ad.png
[System.arraycopy_]: https://blog.csdn.net/li_w_ch/article/details/111240654

发表评论取消回复

表情：

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

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

相关阅读

相关合并两个有序数组

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

我就是我/ 2024年04月06日 10:21/ 0 赞/ 61 阅读

相关算法：合并两个有序数组---双指针[1]

![在这里插入图片描述][901cb5a6d22247e4a1b2fcb20c6adfe5.png_pic_center] 1、题目：给你两个按非递减顺序排列的整

男娘i/ 2024年03月26日 23:14/ 0 赞/ 53 阅读

相关 leetcode 88.合并两个有序数组（双指针 java）

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的

蔚落/ 2023年08月17日 17:01/ 0 赞/ 78 阅读

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

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

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

相关使用双指针合并两个有序数组

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

青旅半醒/ 2022年12月28日 11:22/ 0 赞/ 75 阅读

相关合并两个有序数组

合并两个有序数组 1、参考资料 https://leetcode-cn.com/problems/merge-sorted-array/ 2、题目要求 >

绝地灬酷狼/ 2022年12月08日 05:15/ 0 赞/ 207 阅读

相关两个有序数组合并成一个有序数组

两个有序数组合并成一个有序数组 1. 题目描述数组a是有序的，数组b也是有序的，如何高效地合并它们成一个数组，并且新数组也是有序的？ 2.

冷不防/ 2022年08月06日 02:11/ 0 赞/ 228 阅读

相关两个有序数组合并成一个有序数组

思想：先依次比较两个数组，按照小的就传入新的数组。当这次比较完之后可能有一个数组的长度很长，留下一些数组，然后在新数组的末尾插入即可。代码： pub

亦凉/ 2022年08月04日 08:39/ 0 赞/ 263 阅读

相关合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的

╰半夏微凉°/ 2022年04月16日 06:11/ 0 赞/ 278 阅读

相关合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2

一时失言乱红尘/ 2021年11月16日 12:52/ 0 赞/ 355 阅读