题目:
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1
中。为了应对这种情况,nums1
的初始长度为 m + n
,其中前 m
个元素表示应合并的元素,后 n
个元素为 0
,应忽略。nums2
的长度为 n
。
构思:
想法一:
先合并再排序
因为nums1空间为两个数组个数的和,所以可以将数组直接合并,再用之前学过的sort函数直接排序。
时间复杂度会以为排序变得较大
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}
};
作者:力扣官方题解
想法二:
看了力扣的官方题解,如果不是官方标签写着双指针。
点赞最高的是利用双指针逆向求解,感觉方法很棒,看了一下大概思路,再自己手动敲一下代码,对比一下不同。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = nums1.size()-1;
m--;
n--;
while(n>=0){
while(m>=0 && nums1[m]>nums2[n]){
swap(nums1[m--],nums1[i--]);
}
swap(nums2[n--],nums1[i--]);
}
}
};
和原代码基本一致,因为nums1数组的空间都在后面,而且是升序排列,所以可以从后往前进行比较,1比2大的情况下1和尾部交换,1比2小或者相等的情况下2和尾部交换。
此代码块为力扣点赞数最多的题解,准确有效。
在此补充想法一遇到的两个小问题,因为作者很久没用C++,一些概念比较模糊,趁此机会再熟悉一下知识。
-
for循环++i和i++
for循环中i++:java中i++是先返回i的值后再自增i,所以在每次for循环时都会花费额外的内存和时间去开辟新的临时变量空间来转存,故其效率会更低。
for循环中++i:java中++i是直接将i自增后再返回,省去了开辟新的临时变量的额外消耗,故其效率比i++高。
-
容器for循环需要的条件是不等于,因为cpp中许多的STL容器都定义了迭代器与!=运算符,而绝大多数没有定义< 运算符与下标运算,考虑到编程风格的通用性(在标准库提供的所有容器都有效),只要我们养成使用迭代器与!=的习惯,就不用太在意用的是哪种容器类型。
对于容器与迭代器的理解会专门写一篇文章来重新熟悉一下
标签:思维过程,++,数组,--,int,有序,nums1,nums2 From: https://www.cnblogs.com/isku-ran/p/17093148.html