递增排列的数组 union all
假设有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);
}

运行程序输出为：abbbccfgjmopqttuvwz

可以看到和预期一模一样。
分析这个算法的渐进时间复杂度，实际上我们发现他只是一个单循环，很明显我们原操作只是c[h]=a[n];这样的复制
所以时间复杂度为：
T(n)=O(n)
但是这样的算法明显依赖于两个数组排序好了的情况

ITPub博客

数据结构：递增排列的数组 union all 算法 2.1

最新文章