algorithm - 将整数列表打印为从外部到内部的三角形的最快方法

Question

考虑以下问题:

您收到一些整数 m 并设置 n=1+2+...+m,

现在您需要将所有从 1 到 n 的数字打印为从外到内的三角形。

例子:

输入:

m=6
n=1+2+3+4+5+6 = 21

输出:

1
2 15
3 16 14
4 17 21 13
5 18 19 20 12
6  7  8  9 10 11

如果可以使用任何支持的数据结构，最快的方法是什么？如果不能使用超过 O(1) 的内存，最快的方法是什么？

Answer 1

@groovy:我想在你的帖子中添加评论，但我不能(我是新来的)。我认为该功能可以简化为:

var a=0;
var atemp=0;
var edge=0;
function cal(x,y,m){
    a=Math.min((y-x),(x),(m-1-y));
    atemp=(((m+(m-3*a+1))*3*a)/2);
    edge=m-3*a;
    if(a==x){
        return atemp+1+y-a*2;
    }else if(a==m-1-y){
        return atemp+edge+x-a;
    }else{
        return atemp+edge*2-2+m-y-a;
    }
}

原谅我不习惯起好名字，手头没有编译器所以用JS写的，O(1)内存为:

a (minimum number of the position to the bottom, left and right), 
atemp (the total number of the outer loops of triangle caused i.e. for m=4, when we print number 10, 1-9 forms the outer loop of triangle and atemp is 9), 
edge (the edge is the longest edge of the current triangle)

只有 O(n) 的时间复杂度让你通过嵌套循环打印出所有数字(没有填充)，比如(不是 JS):

for(i=0;i<m;i++){ for(j=0;j<=i;j++) print cal(j,i,m); print '\n'}

(ps.我不懂hashkell，不过我猜你的思路大概是这样的，有漏掉的请指出)