JavaScript 如何高效构建 reverse lookup 反向查找数组？

数据老陈

2026-9-27

JavaScript 反向查找数组高效实现方案

场景说明

我们需要构建的反向查找数组满足以下规则：

输入为长度为n的1~n不重复排列数组
输出数组output满足：若输入数组第i位（从0计数）的值为v，则输出数组第v-1位的值为i+1
转换示例：[5, 3, 1, 4, 2] => [3, 5, 2, 4, 1]

最优实现思路

这种场景下时间复杂度最低就是O(n)，因为必须遍历所有输入元素完成映射，你给出的基础循环版本已经达到了时间复杂度最优，我们可以基于它做兼容性、健壮性的优化：

1. 基础最优版本（时间复杂度O(n)，空间复杂度O(n)）

const input = [5, 3, 1, 4, 2];
// 预先初始化数组长度，避免动态扩容带来的性能损耗
const output = new Array(input.length);
// 避免声明全局变量i
for (let i = 0; i < input.length; i++) {
    output[input[i] - 1] = i + 1;
}

注意：这个版本仅适用于输入是1~n无重复排列的场景，如果输入存在非数字、超出长度范围的值、重复值，需要加校验逻辑。

2. 带校验的健壮版本

如果输入可能不符合1~n排列的规则，可以增加校验避免输出异常：

function buildReverseLookup(input) {
    const n = input.length;
    const output = new Array(n);
    const seen = new Set();
    for (let i = 0; i < n; i++) {
        const val = input[i];
        // 校验值合法性
        if (typeof val !== 'number' || val < 1 || val > n || seen.has(val)) {
            throw new Error('输入数组必须是1~n的不重复数字排列');
        }
        seen.add(val);
        output[val - 1] = i + 1;
    }
    return output;
}

3. 函数式写法（可读性优先，性能和循环版本几乎无差异）

如果你偏好函数式风格，可以用Array.prototype.reduce实现：

const input = [5, 3, 1, 4, 2];
const output = input.reduce((acc, cur, idx) => {
    acc[cur - 1] = idx + 1;
    return acc;
}, new Array(input.length));