LeetCode 88. 合并两个有序数组题目描述给你两个按非递减顺序排列的整数数组 nums1 和 nums2另有两个整数 m 和 n分别表示 nums1 和 nums2 中元素的数目。请你合并 nums2 到 nums1 中使合并后的数组同样按非递减顺序排列。注意最终结果不返回而是存储在 nums1 中。nums1 的初始长度为 m n其中前 m 个元素为有效数据后 n 个元素为 0 占位。思路从后往前双指针如果从前往后合并会覆盖 nums1 中尚未处理的元素需要额外数组。更优做法是从后往前填充· 指针 i 指向 nums1 有效部分的末尾m - 1· 指针 j 指向 nums2 的末尾n - 1· 指针 k 指向 nums1 的末尾m n - 1每次比较 nums1[i] 和 nums2[j]将较大的放到 nums1[k]然后相应指针前移。这样不会覆盖未处理的元素。Java 实现classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){intim-1;// nums1 有效元素末尾intjn-1;// nums2 末尾intkmn-1;// 合并后数组末尾while(j0){// 如果 nums1 还有元素且大于 nums2 当前元素if(i0nums1[i]nums2[j]){nums1[k--]nums1[i--];}else{nums1[k--]nums2[j--];}}// 若 nums2 处理完nums1 剩余元素本就在正确位置无需处理}}复杂度分析指标 复杂度时间复杂度 O(m n)每个元素最多处理一次空间复杂度 O(1)原地修改关键点从后往前避免覆盖 nums1 中未比较的元素。循环条件只需 j 0当 nums2 全部合并完后nums1 剩余元素已经在正确位置。相等时放 nums2[j] 或 nums1[i] 都可以不影响非递减顺序。示例验证输入nums1[1,2,3,0,0,0],m3nums2[2,5,6],n3过程· 比较 3 和 6 → 放 6nums1 [1,2,3,0,0,6]· 比较 3 和 5 → 放 5nums1 [1,2,3,0,5,6]· 比较 3 和 2 → 放 3nums1 [1,2,3,3,5,6]· 比较 2 和 2 → 放 2nums1 [1,2,2,3,5,6]最终结果[1,2,2,3,5,6]