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

概述为了性能,在O(n ^ 2)算法中,我希望将复杂度降低两倍.基本上,我有这种形状的结构： 0 1 2 3 4 5----------------------0 | 11, 2 | 23, 4, 5 | 36, 7, 8, 9 | 410, 11 为了性能,在O(n ^ 2)算法中,我希望将复杂度降低两倍.基本上,我有这种形状的结构：

0   1   2   3   4   5----------------------0                     | 11,2                 | 23,4,5             | 36,7,8,9         | 410,11,12,13,14    | 515,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)中计算的方法.它存在吗？

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

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

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

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

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

那么较小的索引就是：

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

总结

以上是内存溢出为你收集整理的巧妙地计算数组中的位置(C)全部内容，希望文章能够帮你解决巧妙地计算数组中的位置(C)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。