两个数组合并的算法--有没有更好的想法?
突然看到以前的一个题目,是这样子的:
已知按逆序的整型数组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))?
Skyrail
10 years, 9 months ago
Answers
/*
直接合并插入即可,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