如何基于坐标对角填充2D数组

Question

我正在构建一个类似热图的矩形阵列接口,我希望"热"位置位于数组的左上角,而"冷"位置位于右下角.因此,我需要一个对角填充的数组,如下所示:

    0    1    2    3
  |----|----|----|----|
0 | 0  | 2  | 5  | 8  |
  |----|----|----|----|
1 | 1  | 4  | 7  | 10 |
  |----|----|----|----|
2 | 3  | 6  | 9  | 11 |
  |----|----|----|----|

所以实际上,我需要一个函数f(x,y)

f(0,0) = 0
f(2,1) = 7
f(1,2) = 6
f(3,2) = 11

(或者,当然,类似的函数f(n)其中f(7)= 10,f(9)= 6等).

最后,是的,我知道这个问题类似于这里,这里和这里提出的问题,但那里描述的解决方案只是遍历而不填充矩阵.

Answer 1

如果您仅限于逐行浏览数组，那么这将是一个有趣的问题。我将矩形分为三个区域。左上角的三角形，右下角的三角形，中间的菱形。

对于左上角的三角形，第一列 (x=0) 中的值可以使用常见的算术级数 来计算1 + 2 + 3 + .. + n = n*(n+1)/2。该三角形中具有相同 x+y 值的字段位于同一对角线中，并且该值是第一列 + x 的总和。

同样的方法适用于右下角的三角形。但不是使用xand y，而是使用w-xand h-y，其中w是矩形的宽度和h高度。必须从w*h-1数组中的最高值中减去该值。

中间的菱形有两种情况。如果矩形的宽度大于（或等于）高度，则矩形的左下字段是菱形中具有最低值的字段，并且可以计算之前的和h-1。从这里开始，您可以想象菱形是一个矩形，其 x 值为x+y，y 值为y原始矩形。因此，计算该新矩形中的剩余值很容易。
在另一种情况下，当高度大于宽度时，可以使用该算术和来计算 和 处的字段x=w-1，y=0并且可以将菱形想象为具有 x 值x和 y 值的矩形y-(w-x-1)。

例如，可以通过预先计算值来优化代码。我认为所有这些情况都有一个公式。或许我以后再考虑吧。

inline static int diagonalvalue(int x, int y, int w, int h) {
    if (h > x+y+1 && w > x+y+1) {
        // top/left triangle
        return ((x+y)*(x+y+1)/2) + x;
    } else if (y+x >= h && y+x >= w) {
        // bottom/right triangle
        return w*h - (((w-x-1)+(h-y-1))*((w-x-1)+(h-y-1)+1)/2) - (w-x-1) - 1;
    }

    // rhomboid in the middle
    if (w >= h) {
        return (h*(h+1)/2) + ((x+y+1)-h)*h - y - 1;
    }
    return (w*(w+1)/2) + ((x+y)-w)*w + x;
}

for (y=0; y<h; y++) {
    for (x=0; x<w; x++) {
        array[x][y] = diagonalvalue(x,y,w,h);
    }
}

当然，如果没有这样的限制，类似的事情应该更快：

n = w*h;
x = 0;
y = 0;
for (i=0; i<n; i++) {
    array[x][y] = i;
    if (y <= 0 || x+1 >= w)  {
        y = x+y+1;
        if (y >= h) {
            x = (y-h)+1;
            y -= x;
        } else {
            x = 0;
        }
    } else {
        x++;
        y--;
    }
}