2025/10/01
这道题就是归并排序的最后一步,直接就可以想出来;但它看似考察这个,实际上考验了一些额外的技巧,要完全实现出来还是有一定难度。
但是题目有一个额外要求,就是要在第一个数组上进行操作。我一开始在 LeetCode 上尝试不原地的做法,然后把结果复制回去第一个数组,结果直接失败了,我怀疑 LeetCode 是在检测那一块的内存,而不是检测变量。
原地修改第一个数组并不容易,如果用下标遍历的话,因为要边遍历边修改,下标就会乱掉。这道题还加了一个细节限制,就是第一个数组的长度是 m + n,其中后 n 个元素是空的,供合并使用。这属于一个提示。
所以这个非常技巧性的从后往前遍历的思路就出来了,因为后面的元素是空的,可以直接放置合并后的结果,它的速度也永远追不上前面的元素,不会影响前面的元素。