合并有序数组问题

深碍√TFBOYSˉ_ 2022-03-19 05:58 189阅读 0赞

**感谢：感谢大家提出问题，首先对有问题的算法抱歉，文章中已经修改了代码的实现，欢迎大家再次提出问题。**

**有这样一个问题，现在有两个有序的数组，第一个数组的空间足够容纳两个有序数组中的数，利用高效的方法把两个数组合并，并使得数组是有序的，且最后得到的是第一个数组，同时不借助其他额外的存储空间。**

**其实这种题的解法几乎都是一样的，都是从最后一个数开始，这就是取极值的思想，因为数组是有序的，所以，每个数组中最大的那个数一定在数组的末尾。**

**这里，先贴出代码，之后再讲解原理：**

#include <stdio.h>void insert(int *array1, int len1, int *array2, int len2);int main(int argc, char **argv){ int array1[128] = {
        2, 3, 4, 7, 9, 10, 12}; int array2[8] = {
        1, 5, 11, 12, 14, 16, 18, 20}; int i = 0; insert(array1, 7, array2, 8); for(i = 0; i < 15; i++) {  printf("%d ", array1[i]); } printf("\n"); }void insert(int *array1, int len1, int *array2, int len2){ int array1_pos = len1 - 1; int array2_pos = len2 - 1; int new_pos = len1 + len2 - 1; if (array1 == NULL || array2 == NULL)  return; while (array2_pos >= 0 && array1_pos >= 0) {  if (array1[array1_pos] <=  array2[array2_pos])  {   array1[new_pos--] = array2[array2_pos--];  }  else  {   array1[new_pos--] = array1[array1_pos--];  } } while (array2_pos >= 0) {  array1[new_pos--] = array2[array2_pos--]; } return;}

**从代码中可以看出，首先在大的数组中找到合并后数组最后一个数字的位置，之后依次比较两个数组中尾部的值，并根据大小放入不同的位置，最后，直到一个数组的指针指向了负值则结束，这个算法的时间复杂度是 O(m + n)**

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow]

[https_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485