求时间复杂度为O(n)的JavaScript数值数组降序索引提取最优方案

首先得跟你明确一点：如果数组里的数值没有范围限制（比如可能是超大整数、负数或者浮点数），那严格O(n)的时间复杂度是做不到的——因为基于比较的排序算法时间复杂度下界就是O(n log n)，你原来写的方法用到了sort，时间复杂度就是O(n log n)，这在通用场景下已经是比较优的方案了。

不过，如果你的数组满足数值是非负整数，且取值范围不大（比如数值都在0到1000之间），那我们可以用**计数排序（桶排序的一种）**的思路来实现近似O(n)级别的时间复杂度，具体思路是：

1. 先找到数组中的最大值，创建对应数量的"桶"，每个桶用来存对应数值的所有索引；
2. 一次遍历原数组，把每个元素的索引放到对应数值的桶里；
3. 从最大值对应的桶开始，依次把每个桶里的索引收集到结果数组中，这样就能得到按数值降序排列的索引了。

直接上代码示例：

function getSortedIndices(arr) {
  if (arr.length === 0) return [];
  
  // 找出数组中的最大值
  const maxVal = Math.max(...arr);
  // 创建桶数组，每个桶初始化为空数组
  const buckets = new Array(maxVal + 1).fill().map(() => []);
  
  // 一次遍历，把索引放到对应数值的桶里
  for (let i = 0; i < arr.length; i++) {
    buckets[arr[i]].push(i);
  }
  
  // 从最大值到0遍历桶，收集所有索引
  const result = [];
  for (let val = maxVal; val >= 0; val--) {
    if (buckets[val].length > 0) {
      result.push(...buckets[val]);
    }
  }
  
  return result;
}

// 测试你的例子
console.log(getSortedIndices([3, 4, 5, 1, 2])); // 输出 [2,1,0,4,3]，符合预期

这个方法的时间复杂度是O(n + k)，其中k是数组中的最大值。如果k和n的大小差不多（比如数组数值范围在0到n之间），那就能近似看成O(n)的时间复杂度。

但如果你的数组数值范围很大（比如出现1e9这样的数），那创建这么大的桶数组会占用极大的内存，完全不现实。这种情况下，你原来的方法其实已经是最优解了，还可以简化成链式调用的写法：

const maxValueIndexes = (array) => 
  array
    .map((val, idx) => ({ val, idx }))
    .sort((a, b) => b.val - a.val)
    .map(item => item.idx);

总结一下：

• 通用场景下，O(n log n)的方法是最优的，没有严格O(n)的解法；
• 只有当数值范围有限且不大时，才能用计数排序实现近似O(n)的效果。

备注：内容来源于stack exchange，提问作者Areza-s1011