88. 合并兩個(gè)有序數(shù)組
描述
- 給定兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個(gè)有序數(shù)組耗拓。
說明
- 初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n次询。
- 你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2中的元素贸呢。
示例
輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出:
[1,2,2,3,5,6]
思路
- 利用一個(gè)臨時(shí)數(shù)組保存有序結(jié)果赂苗，然后在拷貝回nums1
- 將空間復(fù)雜度降低為O(1)，與在數(shù)組中間插入一個(gè)元素的思想類似贮尉，從后往前來拌滋。將最大的元素放在num1[m+n-1]的位置。
Tips
- 想到初步解后不要立即查詢最優(yōu)解猜谚，要多思考败砂，至少要有一個(gè)是否能否更優(yōu)解的判斷。
- 一般來說要從3個(gè)角度去思考魏铅，時(shí)間復(fù)雜度昌犹、空間復(fù)雜度、代碼簡(jiǎn)潔程度览芳。
class Solution_88_01 {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> nums;
int i = 0, j = 0;
while (i < m && j < n) {
if (nums1[i] < nums2[j]) {
nums.push_back(nums1[i]);
++i;
} else {
nums.push_back(nums2[j]);
++j;
}
}
while (i < m) nums.push_back(nums1[i++]);
while (j < n) nums.push_back(nums2[j++]);
for (int i = 0; i < nums.size(); ++i) nums1[i] = nums[i];
}
};
class Solution_88_02 {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int len = m + n - 1;
--m;
--n;
while (m >= 0 && n >= 0)
nums1[len--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
// while (m >= 0) nums1[len--] = nums1[m--]; 可以不需要
while (n >= 0) nums1[len--] = nums2[n--];
}
};
