递增排列的数组 union all
假设有2个线性表，递增排列的数组，如
char a[20]="abbcopqtuwz";
char b[20]="bcfgjmtv";
我们需要实现一个union all，将两个字符串中的字符合并到
一个新的线性表c中，其中也是按照递增排列的。
那么按照我们要求输出应该为
abbbccfgjmopqttuvwz
那么算法如下：
运行程序输出为：abbbccfgjmopqttuvwz
假设有2个线性表，递增排列的数组，如
char a[20]="abbcopqtuwz";
char b[20]="bcfgjmtv";
我们需要实现一个union all，将两个字符串中的字符合并到
一个新的线性表c中，其中也是按照递增排列的。
那么按照我们要求输出应该为
abbbccfgjmopqttuvwz
那么算法如下：
点击(此处)折叠或打开
- #include<stdio.h>
- #include <string.h>
-
-
- int main(void)
- {
- char a[20]="abbcopqtuwz";
- char b[20]="bcfgjmtv";
-
- char c[30];
- memset(c,0,30);
-
- int n=0;
- int m=0;
- int h=0;
-
- int a_len=strlen(a);
- int b_len=strlen(b);
-
- while(n<a_len && m<b_len)
- {
- if(a[n]< b[m])
- {
- c[h]=a[n];
- n++;
- }
- else if(a[n]==b[m])
- {
- c[h]=a[n];
- n++;
- }
- else
- {
- c[h]=b[m];
- m++;
- }
- h++;
- }
-
- if(a[n] != 0)
- {
- while(n<a_len)
- {
- c[h]=a[n];
- n++;
- h++;
- }
- }
-
- if(b[m] != 0 )
- {
- while(m<b_len)
- {
- c[h]=b[m];
- m++;
- h++;
- }
- }
-
-
- printf("%s\n",c);
- }
可以看到和预期一模一样。
分析这个算法的渐进时间复杂度，实际上我们发现他只是一个单循环，很明显我们原操作只是 c [ h ] = a [ n ] ;这样的复制
所以时间复杂度为：
T(n)=O(n)
但是这样的算法明显依赖于两个数组排序好了的情况
分析这个算法的渐进时间复杂度，实际上我们发现他只是一个单循环，很明显我们原操作只是 c [ h ] = a [ n ] ;这样的复制
所以时间复杂度为：
T(n)=O(n)
但是这样的算法明显依赖于两个数组排序好了的情况
