从外部到内部打印整数列表的最快方法

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,但我想你的想法是这样的,如果我错过了任何案例,请指出)

Answer 2

如果您假设尾调用优化可以防止调用堆栈不必要地增长,那么这是一种使用恒定内存量的方法.(代码是Python,但不使用任何不易移植的构造)

#returns the value at the given position in the triangle of a particular size.
def valueAt(x,y,size):
    #is position out of bounds?
    if x >= size or y >= size or x > y:
        return None
    #is position on the left edge of the triangle?
    if x == 0:
        return y+1
    #is position on the bottom edge of the triangle?
    if y == size - 1:
        return x + size
    #is position on the right edge of the triangle?
    if x == y:
        return 3*size - 2 - x
    #position must lie somewhere within the triangle.
    return 3*size - 3 + valueAt(x-1, y-2, size-3)

这是一个递归函数,其前四个条件构成基本情况.如果坐标位于边界之外或三角形的边缘,我们可以很容易地找到那里的值.如果坐标位于三角形的内部,我们将大三角形像洋葱一样剥离,显示三个尺寸较小的三角形,并从中检索出值.

然后,您可以通过迭代必要的坐标来获取这些值并打印它们.

#adds spaces to the start of the string.
def pad(v, amt):
    while len(v) < amt:
        v = " " + v
    return v

def showTriangle(size):
    #figure out how many characters long each value should be, 
    #based on the length of the largest number
    maxValue = size * (size+1) / 2
    maxLength = len(str(maxValue))

    for y in range(size):
        print "\n",
        for x in range(y+1):
            val = valueAt(x,y,size)
            if val:
                print pad(str(val), maxLength),

for i in range(3, 12+1, 3):
    showTriangle(i)
    print "\n"

结果:

1
2 6
3 4 5


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


 1
 2 24
 3 25 23
 4 26 39 22
 5 27 40 38 21
 6 28 41 45 37 20
 7 29 42 43 44 36 19
 8 30 31 32 33 34 35 18
 9 10 11 12 13 14 15 16 17


 1
 2 33
 3 34 32
 4 35 57 31
 5 36 58 56 30
 6 37 59 72 55 29
 7 38 60 73 71 54 28
 8 39 61 74 78 70 53 27
 9 40 62 75 76 77 69 52 26
10 41 63 64 65 66 67 68 51 25
11 42 43 44 45 46 47 48 49 50 24
12 13 14 15 16 17 18 19 20 21 22 23

编辑:如果您的特定系统没有实现尾调用优化,您可以自己实现迭代形式:

def valueAt(x,y,size):
    acc = 0
    while True:
        #is position out of bounds?
        if x >= size or y >= size or x > y:
            return None
        #is position on the left edge of the triangle?
        if x == 0:
            return acc + y+1
        #is position on the bottom edge of the triangle?
        if y == size - 1:
            return acc + x + size
        #is position on the right edge of the triangle?
        if x == y:
            return acc + 3*size - 2 - x
        #position must lie somewhere within the triangle.
        acc += 3*size - 3
        x-= 1
        y -= 2
        size -= 3