[算法]数列排序

soloforce

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

建议把代码用代码标签包围起来：
[c o d e] xxx  [/ c o d e]
就能够保持缩进空格，便于阅读

Iambitious

狂汗。。。。。。。。。。。。。。。
不懂bbs阿。
谢谢版主提醒,还有谢谢ak70的提示，一开始程序写的有问题，笔误不少，主要是由于没有真正实现此程序，这次应该没有问题了，起码编译应该能通过了，哎，越来越懒了。

Iambitious

最后补上一句，如果要求的是所有不想同的和的最大的n个数，那么只要将for循还体改变一下，变成:

2. count = 0;
3. oldval = 1 + A[n - 1] + B[n - 1];// make oldval and A[n-1] + B[n-1] different
4. while(count < n){
5.    ......
6.    if(oldval != tmp.val)
7.    {
8.       oldval = tmp.val;
9.       count++;
10.    }
11. }

复制代码

即可。

ak70

还是有问题吧？“对于当前选出的最小元素A + B[j]而言，下一个最小的元素的选择必然包括A[i - 1] + B[j]还有A + B[j - 1]”对这个结论我有些怀疑，我看看能否给出反例。

ak70

还用我上面的那个例子，我想可以证明“对于当前选出的最小元素A + B[j]而言，下一个最小的元素的选择必然包括A[i - 1] + B[j]还有A + B[j - 1]”不对。

Iambitious

我还是再解释一下,原来说的有些不太清楚。
对于此题来说，假设队列中有m个值，这个时候在此m个值中选出的最小元素是A与B[j]的和，那么下一个最小元素就必然存在于当前队列剩余的元素以及A[i - 1] + B[j]和A + B[j - 1]之中，这是因为对于所有的A[ki] + B[kj] ki <= i - 1, kj <= j - 1都有A[ki] + B[kj] < A[i - 1] + B[j]或者A[ki] + B[kj] < A + B[j - 1]，所以只需要往优先级队列中添加这两个元素即可。

Iambitious

对于A={10,9,4,3,1}=B这个例子是可以通过的，步骤如下：
1.
q: (20,4,4)||
remove (20,4,4)
print 20
2.
q: (19,4,3) (19,3,4)||
remove (19,4,3)
print 19
3.
q: (18,3,3) (14,4,2) || (19,3,4)
remove (19,3,4)
print 19
4.
q: (14,2,4) || (18,3,3) (14,4,2)
remove (18,3,3)
print 18
5.
q: (13,3,2) (13,2,3) || (14,2,4) (14,4,2)
remove (14,4,2)
print 14
附注：
||前边表示的是新添加的元素，而后边表示的是原来队列的元素。这是求出（包含相同元素）的前n个最大和。

firstddf

我觉得现在的算法还是以对角顶点来确定大小看以下的矩阵

A  B   C  D  E  
F  G   H   I   J
K  L   M  N  O
P  Q  R   S  T
U  V  W  X  Y
现在好像讨论的多是 关于AEYU这种对角的大小，由于他们的关系是和n相关的是有方向性的故容易判断大小，但CW与OK及HR与LN及HR及OK这种非顶点的数怎么能快速的确定大小呢？


这个算题就如同一个迷宫要求从A进从Y出但中间有很大的跳跃性，很难保证字母的排列是和降序有内在联系能够建立某种确定函数关系的。

Iambitious

不太清楚楼上想表达的意思，怎么关联到矩阵了？

firstddf

不好意思说错了，是一个2维数组