最好的机票网站建设,手机建筑网,湖南郴州市房价,网站开发公司网站模板题目地址#xff1a;https://leetcode.cn/problems/merge-sorted-array/description/ 引言#xff1a;话接上回#xff0c;由于上次面试官着急下班#xff0c;面试不得不提前终止#xff0c;这不#xff0c;他又找我去面试了 面试官#xff1a;你好#xff0c;小伙子https://leetcode.cn/problems/merge-sorted-array/description/ 引言话接上回由于上次面试官着急下班面试不得不提前终止这不他又找我去面试了 面试官你好小伙子我们又见面了上次看你的基础还不错所以这次再好好面下你请看下面的题目
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素个数。 请你 合并 nums2到 nums1 中使合并后的数组同样按 非递减顺序 排列。 **注意**最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
for example
输入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 中的元素。我看了下题目思考片刻暂时没有啥头绪先来个笨办法。
我这道题目可以这样先定义一个新的数组长度为 m n m n mn通过两个指针逐个比较两个数组的每一个数按照从小到大的顺序填入新数组最后将新数组的数复制到 nums1 下面是我的代码
public void merge(int[] nums1, int m, int[] nums2, int n) {// 定义两个指针p1,p2分别指向第一个数组和第二个数组的第一个元素int p1 0, p2 0; int[] sorted new int[m n]; // 存储合并后的数组int cur; // 当前遍历到的元素// 遍历两个数组当满足p1 m || p2 n时肯定有数组没有遍历完while (p1 m || p2 n) {if (p1 m) { // 第一个数组已经遍历完直接取第二个数组的元素cur nums2[p2];} else if (p2 n) { // 第二个数组已经遍历完直接取第一个数组的元素cur nums1[p1];} else if (nums1[p1] nums2[p2]) { // 如果第一个数组的当前元素比第二个数组当前元素小则将第一个数组当前元素加入到 sorted 中cur nums1[p1];} else { // 否则将第二个数组当前元素加入到 sorted 中cur nums2[p2];}// 将当前遍历到的元素加入到 sorted 数组中sorted[p1 p2 - 1] cur; }// 将 sorted 数组中的元素复制到 nums1 数组中for (int i 0; i m n; i) {nums1[i] sorted[i];}
}面试官嗯看起来还可以你可以解释下sorted[p1 p2 - 1] cur这句代码吗我不是很懂。
我其实很简单当我们将一个元素加入到sorted数组时我们使用表达式p1 p2 - 1来确定该元素在sorted数组中的索引位置。这是因为我们在每次迭代中只会更新p1或p2的值因此p1 p2的结果减去1就是当前元素在sorted数组中的索引。
面试官O ,懂了你这个算法的时间复杂度是 O ( m n ) O(mn) O(mn) ,空间复杂度也是 O ( m n ) O(mn) O(mn) ,你可以不去引入新的数组来解决这个问题么可不可以就在nums1数组上进行操作呢
我可以的我们直接在nums1上进行操作。 首先定义三个指针 p1、p2 和 p3其中 p1 指向 nums1 中的最后一个元素 m − 1 m - 1 m−1p2 指向 nums2 中的最后一个元素 n − 1 n - 1 n−1 p3 指向合并后数组的最后一个位置 m n − 1 m n - 1 mn−1。如下图所示 我使用 while 循环只要 p1 和 p2 都没有遍历完就进行比较 若 nums1[p1] 大于 nums2[p2]将 nums1[p1] 放入nums1[p3]的位置并将 p1 和 p3 向前移动一位。 若 nums1[p1] 不大于 nums2[p2]将 nums2[p2] 放入nums1[p3]的位置并将 p2 和 p3 向前移动一位。 如果 nums2 中还有元素未加入到nums1数组中再将它们放入nums1数组中。 public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 m - 1; // 指向 nums1 中最后一个元素的索引int p2 n - 1; // 指向 nums2 中最后一个元素的索引int p3 m n - 1; // 指向合并后数组的最后一个位置的索引// 循环比较两个数组中的元素将较大的元素放到nums1[p3]while (p1 0 p2 0) {if (nums1[p1] nums2[p2]) { // 如果 nums1 当前元素大于 nums2 当前元素nums1[p3--] nums1[p1--]; // 将 nums1 当前元素放入nums1数组的末尾p1,p3向前移动} else { // 否则将 nums2 当前元素放入nums1数组的末尾p2,p3向前移动nums1[p3--] nums2[p2--];}}// 如果 nums2 中还有元素未加入到nums1数组中再将剩余的元素放入nums1数组中while (p2 0) {nums1[p3--] nums2[p2--];}
}我上面的算法就没有引入额外的数组只是有少许额外的变量存储指针空间复杂度降到了 O ( 1 ) O(1) O(1) 。
面试官不错不错对这个问题分析的很好思路清晰看来你的数组题目还掌握的不错尤其是利用指针来解决问题。那就回去等等通知吧下一轮面试的时候我们再约时间下一轮的题目可比这一次难哟回家好好准备下。
我好的面试官。下次见
