[算法]数列排序

soloforce · 发表于 2006-7-30 21:34:34

事实上要求的P只有S中最大的前n个元素，那么可以证明构成P中的任一元素的值Val(ab)必定满足：a=A[0] 或者 b=B[0]，基于这个事实，可以用下述算法求P。时间复杂度是O(n)。为了易于描述，主要增设了两个队列数组保存差值，然后通过差值大小来确定P的每个输出值。

[color="Red"]下面的算法仍有bug，行不通，原因见12楼ak70所述

/***************************************
有这样两组数列A[n]和B[n],元素按从大到小顺序排列。
集合S = {(a,b) | a 在数列A中，b在数列B中}.集合中任意一个元素的值为Val(ab)= a + b.
现在求有n个元素的数列P, P中的元素为Val的从大到下排列。请找出一个比较高效的算法。
****************************************/
#include <stdio.h>
/* 计算A[i](i=1,2,3,...,n-1)与A[0]的差值 */
void get_offset(int A[], int offset[], const int n)
{
int i=1;
offset[0]=0;
while(i<n)
{
offset[i]=A[i]-A[0];
++i;
}
}
/* 通过A、B各自的offset值计算P */
void getp(int A[], int B[], int P[], const int n)
{
if(n<1)return; /* n必须大于1 */
int i;
int A_offset[n],B_offset[n];
int pa,pb; /* 分别指向A_offset和B_offset的索引指针 */
get_offset(A,A_offset,n);
get_offset(B,B_offset,n);
P[0]=A[0]+B[0]; /*这个最大，无可非议*/
i=1;
pa=pb=1;
while(i<n)
{
if(A_offset[pa]>B_offset[pb])
{
P[i]=B[0]+A[pa];
++pa;
}
else if(A_offset[pa]<B_offset[pb])
{
P[i]=A[0]+B[pb];
++pb;
}
else
{
P[i]=B[0]+A[pa];
++pa;
++pb;
}
++i;
}
}
int main()
{
const int n=10;
int A[]={20,19,15,10,9,7,5,4,3,1};
int B[]={18,17,15,14,11,10,8,7,6,4};
//int A[]={100,99,98,40,20};
//int B[]={99,60,40,30,28};
int P[n];
getp(A,B,P,n);
int i;
for(i=0;i<n;i++)printf("%d\n",P[i]);
}

复制代码

输出：

~/coding/c $ ./a.out
38
37
35
34
33
31
30
28
27
26

ak70 · 发表于 2006-7-31 00:35:01

“事实上要求的P只有S中最大的前n个元素，那么可以证明构成P中的任一元素的值Val(ab)必定满足：a=A[0] 或者 b=B[0]”，这可能不对吧？比如：A＝｛10，9，4，3，1｝＝B，这种情况下9+9,即A[1]+B[1]就在P中。另外，加法运算是必要的。

yongjian · 发表于 2006-7-31 01:08:32

Post by Lolita
事实上要求的P只有S中最大的前n个元素，那么可以证明构成P中的任一元素的值Val(ab)必定满足：a=A[0] 或者 b=B[0]，基于这个事实，可以用下述算法求P。时间复杂度是O(n)。为了易于描述，主要增设了两个队列数组保存差值，然后通过差值大小来确定P的每个输出值。

#include <stdio.h>
/* 计算A[i](i=1,2,3,...,n-1)与A[0]的差值，adjust用来对差值进行调校 */
void get_offset(int A[], int offset[], const int n, int adjust)
{
int i=1;
offset[0]=0;
while(i<n)
{
      offset[i]=A[i]-A[0]+adjust;
      ++i;
}
}
/* 通过A、B各自的offset值计算P */
void getp(int A[], int B[], int P[], const int n)
{
if(n<1)return; /* n必须大于1 */

int i;
int A_offset[n],B_offset[n];
int pa,pb;  /* 分别指向A_offset和B_offset的索引指针 */

get_offset(A,A_offset,n,0);
get_offset(B,B_offset,n,A[0]-B[0]);

P[0]=A[0]+B[0]; /*这个最大，无可非议*/

i=1;
pa=pb=1;
while(i<n)
{
      /* 或用一行语句 P[i++]= A_offset[pa]>B_offset[pb] ? (B[0]+A[pa++]) : (A[0]+B[pb++]); */
      if(A_offset[pa]>B_offset[pb])
      {
         P[i]=B[0]+A[pa];
         ++pa;
      }
      else
      {
         P[i]=A[0]+B[pb];
         ++pb;
      }
      ++i;
}
}
int main()
{
const int n=5;
int A[]={100,99,98,96,40,1};
int B[]={99,20,10,5,4,3};
//int A[]={100,99,98,40,20};
//int B[]={99,60,40,30,28};
int P[n];
getp(A,B,P,n);
int i;
for(i=0;i<n;i++)printf("%d\n",P[i]);

}
复制代码

输出：

恩，思路是蛮好的，可是仍旧没有解决问题。我构造了一个较为复杂一点的数列来应证我的算法，这里可以改出供大家参考。
A[] = (20,19,15,10,9,7,5,4,3,1)
B[]= (18,17,15,14,11,10,8,7,6,4)
问题：1. 正如ak70所说，off_set相等的情况没有考虑。2. 更为复杂的情况是在下轮，下下轮，等的比较中可能出现比前面大的值。这个要在一次排序中调整，个人感觉难度很大。我是觉得由于数列的组合值不太有规律性，O(n)的可能性似乎不大。

firstddf · 发表于 2006-7-31 06:29:12

这个问题估计不从P全集排而仅从头几个排是不行的，关键是间距值无规律，而验证其周围几轮数是不够的。解决这个问题我想应该找操作系统的源码来看，我记得学汇编时内存存储不是高高低低嘛，而内存地址是从高向低的，他们有相似性，当然这是我的猜想。
我有一个思路就是P集中最大的是A[0]+B0[];最小的是A[n]+B[n];由于这两值是确定的，故间距全长是确定的，那么P中其他的值是在这个间距之中的，只要求的p与(p[0]+p[n])/2的间距,即能确定，靠左靠右的距离了。解决时就用1/2冒泡法，以已知p及(p[0]+p[n])/2为基点则能快速定位了，就能准确知道

soloforce · 发表于 2006-7-31 09:08:03

Post by yongjian
恩，思路是蛮好的，可是仍旧没有解决问题。我构造了一个较为复杂一点的数列来应证我的算法，这里可以改出供大家参考。
A[] = (20,19,15,10,9,7,5,4,3,1)
B[]= (18,17,15,14,11,[color="Red"]19,8,7,6,4)
问题：1. 正如ak70所说，off_set相等的情况没有考虑。2. 更为复杂的情况是在下轮，下下轮，等的比较中可能出现比前面大的值。这个要在一次排序中调整，个人感觉难度很大。我是觉得由于数列的组合值不太有规律性，O(n)的可能性似乎不大。

1、A、B必须是降序排列的，否则应先排好A、B。
2、

Post by ak70

“事实上要求的P只有S中最大的前n个元素，那么可以证明构成P中的任一元素的值Val(ab)必定满足：a=A[0] 或者 b=B[0]”，这可能不对吧？比如：A＝｛10，9，4，3，1｝＝B，这种情况下9+9,即A[1]+B[1]就在P中。另外，加法运算是必要的。

我脑筋生锈了，的确如此。看来我前面那个算法行不通

yongjian · 发表于 2006-7-31 10:34:05

1、A、B必须是降序排列的，否则应先排好A、B。

笔误，改正了。

Iambitious · 发表于 2006-8-1 15:30:04

这个题应该是比较标准的一道ACM题了，其实比较简单，算法复杂度为O(nlogn)。

算法思想如下：
主要参考败者树的思想，维护一个优先级队列，依次提取最小元素，每次查找最小元素的时间是
O(logn),总共需要找出n个最小元素，所以总的时间复杂度为O(nlogn)。

具体算法如下：

数据结构：
PriorityQueue<data> q = new PriorityQueue<data>()存储元素为data类型的优先级队列
boolean vis[n[n]数组：当vis[j] = true时表示A与B[j]的和已经被加入到优先级队列q中。
class data implements Comaparable<data>
{
int val;
indexA i;
indexB j;
public data(int c, int ia, int ib)
{
      this.val = c;
      this.i = ia;
      this.j = ib;
}
public int compare(data o)
{
      return o.val - this.val;//sort by decreasing
}
public String toString(void)
{
      return "" + this.val;
}
}
复制代码
优先级队列中存储的元素。

主体流程(java)：
boolean[][] vis = new boolean[n][n];
PriorityQueue<data> q = new PriorityQueue<data>();
Arrays.sort(A);// sort array A by accending
Arrays.sort(B);// sort array A by accending
q.add(new data(A[n - 1] + B[n - 1], n - 1, n - 1));// add a new element data into the priority queue
vis[n - 1][n - 1] = true;
for (int i = 0; i < n; i++) {
data tmp = q.peek();// get the top element of the priority queue
System.out.println(q.remove());// remove the top element of the priority queue and print its value
if (tmp.i < n - 1 && !vis[tmp.i - 1][tmp.j]) {
q.add(new data(A[tmp.i - 1] + B[tmp.j], tmp.i - 1, tmp.j));
vis[tmp.i - 1][tmp.j] = true;
}
if (tmp.j < n - 1 && !vis[tmp.i][tmp.j - 1]) {
q.add(new data(A[tmp.i] + B[tmp.j - 1], tmp.i, tmp.j - 1));
vis[tmp.i][tmp.j - 1] = true;
}
}
复制代码
辅助：
对于当前选出的最小元素A + B[j]而言，下一个最小的元素的选择必然包括A[i - 1] + B[j]还有A + B[j - 1]，而且由于此算法的特性实际上优先级队列中之存在很少的元素，最多不超过n个元素,这是因为每次删除一个元素最多引入2个元素。

ak70 · 发表于 2006-8-1 18:15:44

不太明白。这里的n是指什么？是集合A或B的元素个数还是S的元素个数？另外j一直是0，有点不太对吧？q中应该有n^2个元素吧？

Iambitious · 发表于 2006-8-1 21:26:42

n为A与B的个数，一开始有个笔误，应该从n-1开始，优先级队列里面不会超过2n个元素，通过程序可以容易看出。

Iambitious · 发表于 2006-8-1 21:37:55

把帖子重新编辑了一下，加入一些注释以及定义，主要当时没考虑到java不是所有人都熟悉的。

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