如果您已经有思路了,或者是N刷了,可以先自己写一遍。
题目分析
给你两个有序整数数组 nums1
和 nums2
,其中 nums1
的长度为 m
加上 nums2
的长度,nums2
的长度为 n
。nums1
的后 n
个位置留空,以容纳 nums2
。要求合并这两个有序数组,使合并后的数组仍然有序。
为了不开辟新数组,只能从后向前填充nums1,这也是解决问题的关键。
解题思路
这里可以使用逆向双指针法:
- 指针
i
指向nums1
数组的最后一个元素,指针j
指向nums2
数组的最后一个元素; - 另外创建一个指针
k
指向合并后的数组的最后一个位置的索引; - 对比i和j指向的元素谁的值比较大则把谁放到nums1[k]处,并移动相应的指针,直到i或者j小于0;
- 最后如果
j
仍然大于等于0,意味着nums2中还有未合并的元素,把这些元素复制到nums1的开头
Java解法
下面是使用Java语言的解法:
1 | public class Solution { |