福建省建设环卫协会网站,wordpress点赞按钮,宁夏建设厅网站旧版,网站建设旗舰品牌88. 合并两个有序数组
难度#xff1a;简单
题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中#xff0c;使合并后的数组同样按 非递减顺序 …88. 合并两个有序数组
难度简单
题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
**注意**最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
示例 1
输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3
输出[1,2,2,3,5,6]
解释需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。示例 2
输入nums1 [1], m 1, nums2 [], n 0
输出[1]
解释需要合并 [1] 和 [] 。
合并结果是 [1] 。示例 3
输入nums1 [0], m 0, nums2 [1], n 1
输出[1]
解释需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意因为 m 0 所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示
nums1.length m nnums2.length n0 m, n 2001 m n 200-10^9 nums1[i], nums2[j] 10^9
**进阶**你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗
个人题解
思路
定义两个指针分别指向 nums1一个指向 nums2 有效位的最后一位再定义指针 cur 指向nums1 的最后一位逐个比较将较大的放在 cur 的位置cur 往左移较大位放完后也左移考虑边界 如果 p1 已经遍历完了 nums1则需要将 p2 左侧位置的数都移到 nums1 位置上去如果 p2 已经遍历完了 nums2则剩下的本来就在 nums1 相应位置无需移动跳出循环即可
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 m - 1;int p2 n - 1;int cur nums1.length - 1;while (cur -1) {if (p1 -1 p2 -1) {nums1[cur--] nums1[p1] nums2[p2] ? nums1[p1--] : nums2[p2--];} else if (p2 -1) {while (p2 -1) {nums1[cur--] nums2[p2--];}} else {break;}}}
}官方题解
方法一直接合并后排序
最直观的方法是先将数组 nums2 放进 nums1 的尾部然后直接对整个数组进行排序。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {for (int i 0; i ! n; i) {nums1[m i] nums2[i];}Arrays.sort(nums1);}
}方法二双指针
方法一没有利用数组 nums1 与 nums2 已经被排序的性质。为了利用这一性质我们可以使用双指针方法。这一方法将两个数组看作队列每次从两个数组头部取出比较小的数字放到结果中。
我们为两个数组分别设置一个指针 p1 与 p2 来作为队列的头部指针。代码实现如下
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 0, p2 0;int[] sorted new int[m n];int cur;while (p1 m || p2 n) {if (p1 m) {cur nums2[p2];} else if (p2 n) {cur nums1[p1];} else if (nums1[p1] nums2[p2]) {cur nums1[p1];} else {cur nums2[p2];}sorted[p1 p2 - 1] cur;}for (int i 0; i ! m n; i) {nums1[i] sorted[i];}}
}方法三逆向双指针
观察可知nums1 的后半部分是空的可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历每次取两者之中的较大者放进 nums1 的后面
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 m - 1, p2 n - 1;int tail m n - 1;int cur;while (p1 0 || p2 0) {if (p1 -1) {cur nums2[p2--];} else if (p2 -1) {cur nums1[p1--];} else if (nums1[p1] nums2[p2]) {cur nums1[p1--];} else {cur nums2[p2--];}nums1[tail--] cur;}}
}作者力扣官方题解 链接https://leetcode.cn/problems/merge-sorted-array/solutions/666608/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
