上三角矩阵主对角线后按对角线遍历的Linear index映射求解

适用场景 #

针对N×N方阵的严格右上角三角区域（即y > x的位置），按对角线偏移量从小到大、同对角线内x从小到大的顺序做0基线性索引，给出从索引k到坐标(x,y)的非递归闭式解。

推导逻辑 #

1. 每条对角线的特征是偏移量d = y - x，取值范围为1 ≤ d ≤ N-1，第d条对角线共包含N - d个元素
2. 前m条对角线的总元素数为等差数列求和：S(m) = m * (2N - m - 1) / 2
3. 对于给定索引k，先求其所在的对角线d：
   解二次方程可得d = floor( ( (2N - 1) - sqrt( (2N - 1)^2 - 8k ) ) / 2 ) + 1
4. 计算k在当前对角线内的偏移量：offset = k - (d - 1) * (2N - d) / 2
5. 最终坐标为x = offset，y = x + d

示例验证（N=4） #

对应用户给出的4×4矩阵示例：

• k=0：d= floor((7 - 7)/2)+1=1，offset=0，x=0,y=1 → 匹配f(0)=(0,1)
• k=1：d= floor((7 - sqrt(49-8))/2)+1=1，offset=1，x=1,y=2 → 匹配f(1)=(1,2)
• k=2：d=1，offset=2，x=2,y=3 → 匹配f(2)=(2,3)
• k=3：d= floor((7 - 5)/2)+1=2，offset=3 - 3=0，x=0,y=2 → 匹配f(3)=(0,2)
• k=4：d=2，offset=1，x=1,y=3 → 匹配f(4)=(1,3)
• k=5：d= floor((7-3)/2)+1=3，offset=0，x=0,y=3 → 匹配f(5)=(0,3)

伪代码实现 #

# 输入：N 矩阵阶数，k 0基线性索引
# 输出：(x,y) 矩阵坐标
def linear_to_coord(N, k):
    sqrt_val = sqrt( (2*N - 1)**2 - 8*k )
    d = int( ( (2*N - 1) - sqrt_val ) // 2 ) + 1
    offset = k - (d - 1) * (2*N - d) // 2
    x = offset
    y = x + d
    return (x, y)

注意事项 #

• k的合法取值范围是0 ≤ k < N*(N-1)/2，超出范围会得到无效坐标
• 计算平方根时建议用整数平方根实现，避免浮点精度误差导致的计算错误

内容的提问来源于stack exchange，提问作者Mat