巧妙地计算数组中的位置(C++)

Question

为了性能,在O(n ^ 2)算法中,我希望将复杂度降低两倍.基本上,我有这种形状的结构:

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

因此,我创建了一个大小的矢量((1+n)*n/2)- 显然,算术和.问题是我现在需要来回计算每个位置.例如,如果我想计算列2和行中的位置,5我可以像这样计算:

int get_position(int x, int y)
{
    int smaller = min(x, y);
    int greater = max(x, y);
    return ((1 + greater) * greater / 2) - greater + smaller;
}

问题是:我怎么能算回来的呢？换句话说,例如从位置号.17我想得到2和6.

或者,也许有更好的方法在C++中做到这一点？(有些结构会让事情变得简单)

编辑 我正在寻找一种在O(1)中计算的方法.它存在吗？

Answer 1

是的,确实存在O(1)解决方案.

在数学上,更大的指数是:

i = [sqrt(2n + 1/4) + 1/2]

(方括号" []"表示截断为整数).

但是,在浮点中正确计算它可能很困难.

那么较小的索引就是:

j = n - i*(i-1) / 2