【C语言】【Leetcode】88. 合并两个有序数组

---

一、题目

链接: link

---

二、思路

这题属于简单题，比较粗暴的做法就是直接比较两个数组，先把第二个数组加到第一个的后面，如何冒泡排序，这种方法简单粗暴但有效，可是不适用于这题，这题要求我们控制时间复杂度在O（m+n）里所以我们可以尝试双指针的方法

但是这里还是用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(m+n)但是同时创立了个数组，所以空间复杂度也变成了O(m+n)

为了不多创建一个新的数组，我们可以利用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;}
}