两个数组合并的算法--有没有更好的想法?


突然看到以前的一个题目,是这样子的:
已知按逆序的整型数组A,B,求合并A、B后的数组C,要求C不能有重复的数字,且包含A、B的所有内容,且按逆排序。已知AB内容有重复。
我的算法是:先把AB整合成一个数组C,再冒泡法遍历数组C排序去除重复数字。
code如下:

   
  #include <stdio.h>
  
#include <stdlib.h>
#include <string.h>

void printfArray(int* array,int len)
{
int i = 0;

for(i = 0 ; i < len ;i++)
{
printf("%d\t",array[i]);
}

printf("\n");

}

void swapValue(int *a , int *b)
{
int temp = 0;

temp = *(a);
*(a) = *(b);
*(b) = temp;
}

void unionArray(int* array1,int len1,int* array2,int len2)
{
int* ret = NULL;

int len = len1+len2;

ret = (int*)malloc(len*sizeof(int));

if(ret == NULL)
{
return;
}

int i = 0;
int j = 0;
int equalNum = 0;
int *p = ret;

//¿½±´Á½¸öÊý×éµÄÄÚÈÝ
memcpy(ret,array1,len1*sizeof(int));
memcpy(ret+len1,array2,len2*sizeof(int));

printfArray(array1, len1);
printfArray(array2, len2);
printfArray(p,len1+len2);

//ðÅÝ·¨ÅÅÐò£¬ÏàͬµÄÁ½¸öÔò½«×îºóÒ»¸ö±ä³É×î´óµÄÖµ
for(i = 0 ; i < len-1; i++)
{
for(j = 0 ; j < len - i -1; j++)
{
if(ret[j+1] <= ret[j])
{
swapValue(ret+j+1,ret+j);
if(ret[j+1] == ret[j])
{
equalNum++;
ret[j+1] = ~(unsigned int)0 / 2;
}
}

}
}

//µÃµ½È¥³ý×î´óÖµºóµÄÊý×é¼´Êǽá¹û
printfArray(p,len1+len2-equalNum);
free(ret);

}

int main(int argc, char** argv)
{
int a[] = {3,5,8,11};
int b[] = {2,6,8,9,11,15,20};

int i = 0;

unionArray(a,sizeof(a)/sizeof(int),b,sizeof(b)/sizeof(int));

return 0;
}

不知道,大伙还有啥好的方法,且时间复杂度最小(o(n*n))?

c 数据结构

Skyrail 10 years, 9 months ago
   
  /*
  
直接合并插入即可,O(n)
很基础的东西。代码很烂,随手写的。意思表达出来就行。
*/

#include <iostream>
#include <cstring>
using namespace std;

int main(int argc, char** argv)
{
int a[5] = {193, 98, 87, 77, 35};
int b[5] = {123, 87, 86, 43, 1};

int* c = new int[10];
memset(c, 0, 40);

// 合并操作
int i = 0;
int j = 0;
int k = 0;
while (i < 5 && j < 5) {
if (a[i] > b[j]) {
c[k++] = a[i];
++i;
} else if (a[i] < b[j]){
c[k++] = b[j];
++j;
} else {
c[k++] = a[i];
++i;
++j;
}
}

while (i < 5) {
c[k++] = a[i];
++i;
}

while (j < 5) {
c[k++] = b[j];
++j;
}

cout << "before merge : " << endl;
cout << "a = ";
for (i = 0; i < 5; ++i) {
cout << a[i] << '\t';
}
cout << "\nb = ";
for (i = 0; i < 5; ++i) {
cout << b[i] << '\t';
}

cout << "\nafter merge :\nc = ";
for (i = 0; i < k; ++i) {
cout << c[i] << '\t';
}
cout << endl;

return 0;
}

東雲研究所 answered 10 years, 9 months ago

Your Answer