建设一个境外网站,3免费做网站,黄骅市住房和城乡建设局网站,怎么注册网店题目
给你两个按非递减顺序排列的整数数组nums1和nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示nums1和nums2中的元素数目。 请你合并nums2到nums1中#xff0c;使合并后的数组同样按非递减顺序排列。 注意#xff1a;最终#xff0c;合并后数组不应由函数返…题目
给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数 m 和 n 分别表示nums1和nums2中的元素数目。 请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。 注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为0 应忽略。nums2 的长度为n。
solution.1 合并之后再进行快排
快排的实现方式和原理
先手写一个快速排序的方法使用了递归的方式这里需要注意的是pivot应该在if语句内部进行赋值否则在nums1和nums2合并之后只有两个元素的情况下会有报错超出索引地址访问报错。然后我们在merge方法中用遍历的方式将nums2插入到nums1的末尾然后使用快速排序。
时间复杂度 由于我们是对两个数组先进行合并然后再快速排序因此长度为mn所以时间复杂度为mnlogmn。 空间复杂度 由于快速排序是一种原地排序方式并没有创建新的数组因此空间复杂度套用快速排序的公式即logmn。
class Solution {
public:void quickSort(vectorint vi, int lo, int hi){int pivot;int i lo;int j hi;if (lo hi){pivot vi[lo];while (i ! j){while (vi[j] pivot j i){j--;}while (vi[i] pivot j i){i;}if(ij){swap(vi[i], vi[j]);}}swap(vi[lo], vi[i]);quickSort(vi, lo, i-1);quickSort(vi, i1, hi);}}void merge(vectorint nums1, int m, vectorint nums2, int n) {for(int i 0;i ! n;i){nums1[mi] nums2[i];}quickSort(nums1, 0, mn-1);}
};solution.2 双指针
使用两个分别指向nums1和nums2数组末端的指针由于题目的设置是nums1后面补齐了0为了给nums2的元素预留位置因此这里的指向nums1数组末端的指针的真正含义是指向nums1最后一个不为0的值的位置然后我们分别比较两个位置的元素的大小从mn-1的位置开始从后往前补齐元素。
时间复杂度 即移动数据的次数最多移动mn次即时间复杂度为mn。 空间复杂度 我们并没有创建新的数组而是在原地进行操作因此空间复杂度为1。
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int p1 m-1;int p2 n-1;int p3 m n - 1;int cur 0;while(p1 0|| p2 0){if(p1 -1){cur nums2[p2--];}else if(p2 -1){cur nums1[p1--];}else if(nums1[p1] nums2[p2]){cur nums1[p1--];}else{cur nums2[p2--];}nums1[p3--] cur;}}
};
