作者：zinghoWU
2026-01-28 16:17:31 星期三
前言
相信有些小伙伴在第一次开启算法大冒险时,碰到的第一个拦路虎就是数组类的题.比如力扣算法第一题 "计算两数之和",以及后续像什么"数组的原地复制"等等,这些题乍一看,一眼"丁真" -- 看上去非常简单.但实际情况是:"题目每个字都看得懂,组合起来就思密达了",或是"拼尽全力,无法战胜,直接GG".诸如此类其实都属正常情况.实不相瞒,本人在做第一个数组相关算法题在看了题解的情况下都鏖战了俩点才看懂,差点直接麻爪,题目如下:
言尽于此,也该引入正题了,在又被折磨了好几个天之后,自认为也是总结了一些"挨打笔记",希望对大家有些帮助
成为糕手第一步 -- 看懂题目
相对于思路的有无,审题也至关重要,很简单,看不懂题目做鸡毛啊.举个栗子,就刚才那个:"非递减顺序"那就是递增呗,合并后也是递增,自然而然就会想到数组复制 -- 恭喜你抓到了关键 所以说看懂了题目,也就是走好了解题的第一步
成为糕手第二步 -- 学会看题解
部分小伙伴刚开始会陷入一种"这个题我一定要用自己的方法弄出来"的状态,有专研的心毫无疑问是值得鼓励的.但我还是推荐刚学习的时候,在毫无思路的情况下多看官方题解,培养解题思维
成为糕手第三步 -- 学会总结反思
据我所知大部分小伙伴都和我一样学习算法都是为了竞赛或者面试,总不能一个一个刷题吧,效率尤为重要.所谓算法大部分都是练出来的,第一见不会,第二次第三次见总会有思路,所以要总结,学会举一反三,做一个类题的经典题和经典解法.
双指针
过完了前置任务,我们把目光聚焦到这个题目上,首先,什么是双指针?豆包是这样说的:
落实到本题中,题目说num1的长度是两个有序数组的元素之和,其实就是要求将num2的元素复制到num1中,再排序输出
暴力解法就是利用先复制再排序,如下:
点击查看代码
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {// 手动复制,将num2的元素复制到num1中,从m+1下标往后排for (int i = 0; i != n; ++i) {nums1[m + i] = nums2[i];}Arrays.sort(nums1); // 调用方法复制/*System.arraycopy(nums2,0,nums1,m,nums2.length);Arrays.sort(nums1);*/
}
这边也贴一下的 System.arraycopy() 方法的使用规制
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
- src 源数组（要从中复制元素的数组）
- srcPos 源数组的起始复制索引（从哪个位置开始复制）
- dest 目标数组（要复制到的数组）
- destPos 目标数组的起始粘贴索引（复制到目标数组的哪个位置）
- length 要复制的元素个数
显然这不是今天的主角,非最优解,但胜在好理解,在本题中可行.双指针做法是此类题官推解法,本体正向,逆向都有可行,思路相同,逆向是最优解,解题如下:
逆向双指针:
我们用两个指针P0和P1分别指向num1数组和num2数组的第最后一个有效元素(num1长度为m+n,但有效元素为m),即,
int P1 = m -1;
int P2 = n -1;
我们的思想是通过P1和P2逆向遍历,末尾元素进行对比,将大的元素放在num1最后位置: m+n-1,定义变量P表示,这样就实现了在num1数组原地遍历的同时实现了排序,空间复杂度为O(1),时间复杂度为O(m+n),优于正向遍历,具体如下:
点击查看代码
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int P = m + n -1; int P1 = m -1; int P2 = n -1; // 循环条件：两个数组都还有未处理的有效元素while (P1 >=0 && P2 >=0){// 比较两个指针指向的元素，把更大的放到nums1的P位置if(nums1[P1]>=nums2[P2]){nums1[P--] = nums1[P1--]; // P1元素更大，放入P位置，P和P1都左移}else{nums1[P--] = nums2[P2--]; // P2元素更大，放入P位置，P和P2都左移}}// 处理nums2剩余的元素（如果有）System.arraycopy(nums2,0,nums1,0,P2+1);}
}