Leetcode笔记目录

88. 合并两个有序数组 Easy

Leetcode笔记目录一、题目描述二、解题过程1.思想2.代码 三、总结

---

一、题目描述

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

输入:

nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

解释: [1,2,2,3,5,6]

提示：

-10^9 <= nums1[i], nums2[i] <= 10^9nums1.length == m + nnums2.length == n

二、解题过程

1.思想

难点在于不能开辟额外空间，查看题解采用倒着确定数组的方法，很好的利用了题目所给的数组结构：

nums1和nums2都按其元素数量从后往前循环；两数组进行比较时，谁大谁被赋值到nums1。若nums2还没有循环到开头，则将其剩下的赋值给nums1。

2.代码

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int pos = m-- + n-- -1; while(m>=0 && n>=0){ nums1[pos--]=nums1[m]>nums2[n]?nums1[m--]:nums2[n--]; } while(n>=0) nums1[pos--] = nums2[n--]; }

---

三、总结

虽然是easy但思想还是没想到，有时候虽然是同一题目，但因为数据的结构问题导致解法不同。