2. 自考
  3. 给定有m个整数的递增有序数组a[1…m]和有n个整数的递减有序数组b[1…n]，试写出算法：将数组a和b归并为递增有序数组c[1…m+n]。(要求：算法的时间复杂度为O(m+n))。

给定有m个整数的递增有序数组a[1…m]和有n个整数的递减有序数组b[1…n]，试写出算法：将数组a和b归并为递增有序数组c[1…m+n]。(要求：算法的时间复杂度为O(m+n))。

admin2014-12-25  102
问题 给定有m个整数的递增有序数组a[1…m]和有n个整数的递减有序数组b[1…n]，试写出算法：将数组a和b归并为递增有序数组c[1…m+n]。(要求：算法的时间复杂度为O(m+n))。
选项
答案 void Merge(int A[]，int B[]，int&C[]，int m，int n) { 将两个递增和递减的数组A和B，合并成一个递增有序的数组c i=0；j=n—1；k=0； while(i=0) if(A[i]<=B[j]) C[k++]=A[i++]； else c[k++]=B[j一一]； while(i=0] c[k++]=B[j--]； }
解析 由于两个数组都有序，但合并得到的新数组C的递增有序，则设两个变量i和j，分别指向数组A的第一个元素和数组B的最后一个元素，将A和B[j]中的小者插入到数组C中，重复上述操作，直到将两个数组中的元素全部合并到数组C为止。算法描述如下。
转载请注明原文地址:https://www.kaotiyun.com/show/k4Vx777K
本试题收录于： 数据结构导论题库理工类分类
0

数据结构导论

理工类

相关试题推荐
随机试题
最新回复(0)