概述
双指针:归并两个有序数组
只是记录自己的刷题过程,答案参考过多种题解。
如有错误感谢指正!
参考:LeetCode 101: A LeetCode Grinding Guide (C++ Version) 作者:高畅 Chang Gao
题目来源:题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台 (leetcode-cn.com)
A. 双指针思想
-
因为这两个数组已经排好序,我们可以把两个指针分别放在两个数组的末尾,即 nums1 的 m − 1 位和 nums2 的 n − 1 位。
-
两个指针对应的值进行比较,每次将较大的那个数字复制到 nums1 的后边,然后向前移动一位。 因为我们也要定位 nums1 的末尾,所以我们还需要第三个指针,以便复制。
-
注意,
nums1 的 m − 1 位
和nums1 的末尾
不是同一位置。
B. 具体实现
-
直接利用 m 和 n 当作两个数组的指针,再额外创立一个 pos 指针,起始位置为 m+n−1。每次向前移动 m 或 n 的时候,也要向前移动 pos。
-
这里需要注意,如果 nums1 的数字已经复制完,不要忘记把 nums2 的数字继续复制;如果 nums2 的数字已经复制完,剩余 nums1 的数字不需要改变,因为它们已经被排好序。
-
++ 和--的小技巧:a++ 和 ++a 都是将 a 加 1,但是 a++ 返回值为 a,而 ++a 返回值为 a+1。如果只是希望增加 a 的值,而不需要返回值,则推荐使用 ++a,其运行速度会略快一些。
C. 思考
-
两个指针指向最后数值位的下标,依次向前 两两比较 ,把数值大的覆盖在末尾。
-
用大于而非大于等于判断(nums1[m] > nums2[n]),是为了能优先结束nums2数组,剩余 nums1 的数字不需要改变,因为它们已经被排好序。
D.代码
public void merge(int[] nums1, int m, int[] nums2, int n) {
int pos = m-- + n-- - 1;
while (m >= 0 && n >= 0) {
nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
}
while (n >= 0) { //如果 nums1 的数字已经复制完,把剩余的 nums2 的数字继续复制
nums1[pos--] = nums2[n--];
}
}
最后
以上就是苹果冬日为你收集整理的LeetCode刷题:双指针 [88.合并两个有序数组] - Java版本的全部内容,希望文章能够帮你解决LeetCode刷题:双指针 [88.合并两个有序数组] - Java版本所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复