百度验证网站所有权,高德地图看不到菲律宾,售后好的品牌策划公司,服务专业的网络建站公司力扣解题-88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中#xff0c;使合并后的数组同样按 非递减顺序 排列。
注意#x…力扣解题-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-109 nums1[i], nums2[j] 109第一次解答解题思路核心方法合并后整体排序先将nums2的元素直接填充到nums1的末尾空闲位置再对整个nums1数组进行排序逻辑极简但未利用数组“有序”的特性存在性能浪费。具体步骤填充nums2到nums1遍历nums2的每个元素共n个将nums2[i]赋值到nums1[mi]的位置nums1的前m位是有效元素后n位是预留的0正好用于存放nums2整体排序调用Arrays.sort(nums1)对合并后的nums1进行升序排序完成非递减排列的要求。性能劣势说明该解法虽然实现了核心功能但未利用题目中“两个数组均为非递减顺序”的关键条件导致性能较差时间复杂度较高排序的时间复杂度为O((mn)log(mn))而利用有序特性的最优解法可做到O(mn)对于mn200的场景排序的额外开销会导致耗时增加4ms仅击败15.63%用户冗余操作明明两个数组已有序却重新对所有元素排序相当于“抛弃已知有序信息从头排序”是对题目条件的浪费内存表现一般虽然无额外空间开销但排序过程中JVM的排序算法双轴快排会产生少量临时空间导致内存消耗43.2MB仅击败36.95%用户。执行耗时:4 ms,击败了15.63% 的Java用户内存消耗:43.2 MB,击败了36.95% 的Java用户publicvoidmerge(int[]nums1,intm,int[]nums2,intn){for(inti0;in;i){nums1[mi]nums2[i];}Arrays.sort(nums1);}第二次解答解题思路核心方法逆向双指针从后往前合并充分利用两个数组“非递减有序”的特性从最大值开始比较将较大值依次放入nums1的末尾避免覆盖未处理的有效元素时间复杂度优化至O(mn)是本题的最优解法。核心原理铺垫由于nums1的末尾有n个空闲位置且两个数组均为升序排列从后往前合并可避免“正向合并时覆盖nums1前m位有效元素”的问题正向合并需额外空间暂存nums1的元素否则会被覆盖而逆向合并直接利用nums1的空闲末尾无需额外空间比较两个数组的“当前最大值”将更大的数放入nums1的当前最末尾逐步向前填充最终得到有序数组。具体步骤边界判断若n0nums2为空无需处理直接返回避免无效的指针操作初始化逆向双指针p1 m - 1指向nums1有效元素的最后一个位置即nums1的最大值位置p2 n - 1指向nums2的最后一个位置即nums2的最大值位置p m n - 1指向nums1的最后一个位置即合并后元素的写入位置逆向合并核心循环p1 0 p2 0比较nums1[p1]和nums2[p2]的大小取较大值写入nums1[p]若nums1[p1] nums2[p2]将nums1[p1]写入nums1[p]p1左移一位p1–继续比较nums1的下一个最大值否则将nums2[p2]写入nums1[p]p2左移一位p2–继续比较nums2的下一个最大值每次写入后p左移一位p–准备写入下一个元素处理nums2剩余元素若循环结束后p2 0说明nums2还有未合并的元素且这些元素均小于nums1已合并的所有元素将nums2[p2]依次写入nums1[p]直到p2 0无需处理nums1的剩余元素因为nums1的剩余元素本就位于nums1的前半部分且已是非递减顺序无需额外操作。核心优化逻辑说明时间复杂度最优仅需一次遍历mn次比较/赋值操作时间复杂度为O(mn)相比排序的O((mn)log(mn))效率提升显著0ms击败100%用户空间复杂度O(1)全程在nums1原数组上操作无额外数组/集合创建内存消耗降至42.9MB击败90.89%用户避免元素覆盖逆向合并的核心优势是“写入位置在未处理元素的后方”不会覆盖nums1前m位的有效元素无需额外空间暂存数据边界处理完善通过if(n!0)跳过nums2为空的情况通过最后的p2循环处理nums2剩余元素覆盖了m0nums1无有效元素等极端场景。执行耗时:0 ms,击败了100.00% 的Java用户内存消耗:42.9 MB,击败了90.89% 的Java用户publicvoidmerge(int[]nums1,intm,int[]nums2,intn){if(n!0){intp1m-1;// nums1 有效部分的最后一个索引intp2n-1;// nums2 最后一个索引intpmn-1;// nums1 总数组的最后一个索引写入位置while(p10p20){intanums1[p1];intbnums2[p2];if(ab){nums1[p]a;p1--;}else{nums1[p]b;p2--;}p--;}//如果nums2的元素还有剩余全部挪过去while(p20){nums1[p]nums2[p2];p--;p2--;}}}总结第一次解答的“合并后排序”思路极简但未利用数组“有序”的特性时间复杂度较高仅适合快速实现功能的场景第二次解答的“逆向双指针”是本题的最优解利用有序特性将时间复杂度优化至O(mn)且原地操作无额外空间开销是对题目条件的充分利用本题的核心解题技巧是逆向思维避开正向合并的“覆盖风险”从最大值开始填充既利用nums1的空闲空间又保证有序性。
