[算法]数列排序

yongjian · 发表于 2006-7-30 03:14:54

有这样两组数列A[n]和B[n],元素按从大到小顺序排列。集合S = {(a,b) | a 在数列A中，b在数列B中}.集合中任意一个元素的值为Val(ab)= a + b. 现在求有n个元素的数列P, P中的元素为Val的从大到下排列。请找出一个比较高效的算法。

soloforce · 发表于 2006-7-30 09:07:16

A[]有n个元素，B[]也是n个元素，P怎么也是n个元素？是不是应该说成是“P有m个元素”？

是不是这个意思：如A[3]={4,3,1}; B[3]={5,3,2}; 则p[7]={9,8,7,6,5,4,3}

firstddf · 发表于 2006-7-30 09:17:17

1 2 3 4 5
1  2 3 4 5 6
2  3 4 5 6 7
3  4 5 6 7 8
4  5 6 7 8 9

S集合应该有不少重值啊，P的元素数量是不是与S元素一样啊，还是和楼上说的只有不重复的

soloforce · 发表于 2006-7-30 09:24:20

一般来说集合要满足互异性

firstddf · 发表于 2006-7-30 11:41:57

估计没有什么好算法，得出不重复的元素值，然后冒泡法
如果元素间的间距值是有规律的也许有好方法

yongjian · 发表于 2006-7-30 14:31:40

S has n^2 of elements and P just contains nth biggest Val. Such as:
S = { (A[1], B[1]), (A[1],B[2]), (A[1],B[3]) ... (A[1],B[n]), (A[2],B[1])...}
P = { (A[1]+B[1]), (A[1]+B[2]), (B[1]+A[2]) ... }

ak70 · 发表于 2006-7-30 16:43:14

生成集合S需要n^2次相加运算。再做排序的话，如果不考虑内存空间问题，可以用merge sort，这样一来排序需要n^2*log(n^2)。我看这个算法的time complexity是O(n^2).不知那位还有更好的？

soloforce · 发表于 2006-7-30 17:55:03

需要生成S吗？
楼主的意思是：集合P中的元素是集合S中的n个最大值。那么求P的元素时直接从A、B中直接获取就可以了。

修正：下面的方法错了，太想当然了

/* 假定A和B已经按降序排列，即A[0]最大, A[n-1]最小，B亦然。从A、B求P */
#include <stdio.h>
void getp(int A[], int B[], int P[], int n)
{
int i=0;
int a,b;
while(i<n)
{
P[3*i]=A[i]+B[i];
if(i+1<n)
{
a=A[i]+B[i+1];
b=B[i]+A[i+1];
P[3*i+1]=(a>b?a:b);
P[3*i+2]=(a>b?b:a);
}
++i;
}
}
int main()
{
const int n=5;
int A[]={22,12,8,4,3,1};
int B[]={17,9,6,5,3,2};
int P[n];
getp(A,B,P,n);
int i;
for(i=0;i<n;i++)printf("%d\n",P[i]);
}

复制代码

输出：

~ $ ./a.out
39
31
29
21
18

firstddf · 发表于 2006-7-30 19:40:09

如果是int A[]={100,99,98,96,40,1};
int B[]={99,20,10,5,4,3};
n=8

得到以下
0,199
1,198
2,120
3,119
4,118
5,109
6,108
7,106

那197呢？195？
就是A[1]+B[0];A[2]+B[0]呢，由于间距不能控制，边角线的算法很难确定对角值为暂时最大的

soloforce · 发表于 2006-7-30 19:53:56

Post by firstddf
如果是int A[]={100,99,98,96,40,1};
int B[]={99,20,10,5,4,3};
n=8

得到以下
0,199
1,198
2,120
3,119
4,118
5,109
6,108
7,106

那197呢？195？
就是A[1]+B[0];A[2]+B[0]呢，由于间距不能控制，边角线的算法很难确定对角值为暂时最大的

哦。是我错了。反思中

		自动登录	找回密码
密码			注册