n×n矩阵主对角线上方元素索引转对应行列的简化算法求解

原理说明 #

主对角线上方的元素按行编号时，第row行（从0开始计数）共有n - 1 - row个元素，前row行的元素总个数为等差数列求和结果：row * (2n - row - 1) / 2。
我们只需要找到满足 row * (2n - row - 1) / 2 ≤ inputIndex 的最大整数row，再计算当前行内的偏移量即可得到列号，整个过程可以通过数学公式直接计算，时间复杂度为O(1)。

实现代码 #

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int inputIndex = 8;
    int n = 5;
    
    // 可选：增加索引合法性校验
    if (inputIndex < 0 || inputIndex >= n*(n-1)/2) {
        cout << "无效索引" << endl;
        return -1;
    }

    // 解二次方程计算行号
    double temp = (2 * n - 1) * (2 * n - 1) - 8 * inputIndex;
    int row = (int)((2 * n - 1 - sqrt(temp)) / 2);
    // 计算当前行内偏移量
    int offset = inputIndex - row * (2 * n - row - 1) / 2;
    int column = row + 1 + offset;
    
    cout << "row = " << row << endl << "column = " << column;
    return 0;
}

方案优势 #

1. 时间复杂度从原实现的O(n)优化到O(1)，n越大性能优势越明显
2. 代码更简洁，没有循环分支逻辑
   如果担心浮点数精度问题（比如n超过1e5的场景），也可以用二分法找符合条件的row，时间复杂度为O(logn)，仍然远优于原循环实现。

验证结果 #

输入inputIndex=8、n=5时，运行输出和原实现一致：

row = 2
column = 4

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