网站游戏网站建设,网站建设课程的认识,网站开发所需要的时间 知乎,网站开发 招聘 龙岩文章目录 一、题目二、思路再思考 一、题目
链接: link 二、思路
这题属于简单题#xff0c;比较粗暴的做法就是直接比较两个数组#xff0c;先把第二个数组加到第一个的后面#xff0c;如何冒泡排序#xff0c;这种方法简单粗暴但有效#xff0c;可是不适用于这题… 文章目录 一、题目二、思路再思考 一、题目
链接: link 二、思路
这题属于简单题比较粗暴的做法就是直接比较两个数组先把第二个数组加到第一个的后面如何冒泡排序这种方法简单粗暴但有效可是不适用于这题这题要求我们控制时间复杂度在Omn里所以我们可以尝试双指针的方法
但是这里还是用qsort函数的方法给大家写一下这种函数的内置排序算法与冒泡类似大家有兴趣可以看一下链接: link
里面的排序过程大致如下
void bubble(void* base, int count, int size, int(*cmp)(void*, void*))
{for (int i 0; i count - 1; i){for (int j 0; j count - i - 1; j){if (cmp((char*)base j * size, (char*)base (j 1) * size) 0){_swap((char*)base j * size, (char*)base (j 1) * size, size);}}}
}然后是整个程序的编写过程
int cmp(int* a, int* b) {return *a - *b;
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {for (int i 0; i ! n; i) {nums1[m i] nums2[i];}qsort(nums1, nums1Size, sizeof(int), cmp);
}双指针顾名思义设立 两个指针锁定两个指针的索引 进行比较小的数放入一个新创立的数组最后再把这个新创立的数组的值赋给num1就行了
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int nums[nums1Size];int p1 0;int p2 0;int tmp; // 用来临时记录当前值while (p1 m || p2 n) {if (p1 m)tmp nums2[p2];else if (p2 n)tmp nums1[p1];else if (nums1[p1] nums2[p2])tmp nums2[p2];elsetmp nums1[p1];nums[p1 p2 - 1] tmp;}for (int i 0; i m n; i) {nums1[i] nums[i];}
}再思考
如何不创立新的数组进行排序呢
如果是上一种方法我们虽然时间复杂度小了下去变成了O(mn)但是同时创立了个数组所以空间复杂度也变成了O(mn)
为了不多创建一个新的数组我们可以利用num1数组后面多出来的那几个0做文章我们在上一种方法中采用的是先把小的取出来但是如果我们先把大的取出来放进num1数组的末尾这样再不创建新的数组的前提下num1数组的元素也不会被覆盖了
代码如下
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 m - 1, p2 n - 1;int tail m n - 1;int cur;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[tail--] cur;}
}
