网站报价收费单,网站排行榜,网站后台上传图片大小,云主机放多个网站目录 题目引用描述1.直接合并 排序2.指针3.后逆向双指针进阶#xff1a;你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗#xff1f;总结 题目
来自力扣
引用 合并两个有序数组 给你两个按 **非递减顺序 **排列的整数数组 nums1 和 nums2#xff0c;另有两个整… 目录 题目引用描述1.直接合并 排序2.指针3.后逆向双指针进阶你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗总结 题目
来自力扣
引用 合并两个有序数组 给你两个按 **非递减顺序 **排列的整数数组 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 n nums2.length n 0 m, n 200 1 m n 200 -109 nums1[i], nums2[j] 109
最直观的方法是先将数组 nums 2放进数组 nums 1 的尾部
然后直接对整个数组进行排序。1.直接合并 排序 class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {for(int i0; i!n; i){nums1[mi]nums2[i];}Arrays.sort(nums1);}
}2.指针
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i m - 1; // 指向 nums1 中最后一个元素的指针int j n - 1; // 指向 nums2 中最后一个元素的指针int k m n - 1; // 指向 nums1 的末尾的指针// 从两个数组的末尾开始比较并合并元素while (j 0) {if (i 0 nums1[i] nums2[j]) {nums1[k] nums1[i--];} else {nums1[k] nums2[j--];}k--;}}
}以下是代码的逻辑和特点 初始化指针 p1 和 p2 分别初始化为 m - 1 和 n - 1指向 nums1 和 nums2 的最后一个元素。 初始化尾部指针 tail 初始化为 m n - 1指向 nums1 数组的末尾位置这是合并后数组的最后一个元素的位置。 循环逻辑 循环继续进行直到 p1 和 p2 至少有一个到达数组的开始位置即 p1 0 或 p2 0。 选择元素 如果 p1 已经到达数组的开始位置即 -1则选择 nums2 中的元素。如果 p2 已经到达数组的开始位置选择 nums1 中的元素。如果两个指针都在数组范围内比较 nums1[p1] 和 nums2[p2] 的值选择较小的元素。 填充尾部 将选择的元素 cur 放入 nums1[tail]然后更新 tail 的位置。 指针更新 根据选择的元素来自哪个数组相应地更新 p1 或 p2 的值。 循环结束 当 p1 和 p2 都到达数组的开始位置时循环结束此时 nums1 已经被成功合并。
这段代码正确地实现了合并两个有序数组的功能并且避免了不必要的排序操作。它使用了双指针技术从两个数组的末尾开始逐步向前合并直到所有元素都被合并到 nums1 中。这种方法的时间复杂度为 O(mn)空间复杂度为 O(1)因为它只使用了常数级别的额外空间。
3.后逆向双指针
public class Solution {// 此方法将nums2合并到nums1中使得nums1成为有序数组public void merge(int[] nums1, int m, int[] nums2, int n) {// p1指向nums1的最后一个实际元素p2指向nums2的最后一个实际元素tail指向合并后nums1的最后一个位置int p1 m - 1, p2 n - 1;int tail m n - 1;int cur; // cur用于存储当前比较的元素// 当nums1和nums2中还有元素未被合并时继续循环while (p1 0 || p2 0) {// 如果nums1已经遍历完直接将nums2中剩余的元素复制到nums1中if (p1 -1) {cur nums2[p2--];} // 如果nums2已经遍历完直接将nums1中剩余的元素复制到nums1中else if (p2 -1) {cur nums1[p1--];} // 如果nums1中的当前元素大于nums2中的当前元素将其复制到nums1的尾部并移动p1指针else if (nums1[p1] nums2[p2]) {cur nums1[p1--];} // 如果nums2中的当前元素大于等于nums1中的当前元素将其复制到nums1的尾部并移动p2指针else {cur nums2[p2--];}// 将cur复制到nums1的tail位置并将tail向前移动nums1[tail--] cur;}}
}进阶你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗 class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {// 创建两个指针分别指向两个数组的开头int p1 0, p2 0;// 创建一个临时数组来存储合并后的结果int[] temp new int[m n];// 创建一个指针指向临时数组的开头int p 0;// 循环遍历两个数组直到其中一个数组遍历完毕while (p1 m p2 n) {if (nums1[p1] nums2[p2]) {temp[p] nums1[p1];} else {temp[p] nums2[p2];}}// 如果 nums1 数组还有剩余元素将其全部复制到临时数组中while (p1 m) {temp[p] nums1[p1];}// 如果 nums2 数组还有剩余元素将其全部复制到临时数组中while (p2 n) {temp[p] nums2[p2];}// 将临时数组的元素复制回原始数组 nums1System.arraycopy(temp, 0, nums1, 0, m n);}
}总结
一天的学习结束啦晚上可以休息啦。明天见
