基于整数属性值对对象数组排名的优化算法需求

你当前的方案对每个属性单独排序再赋值排名，两次排序的时间复杂度都是O(n log n)，整体复杂度为O(n log n)。如果想进一步优化，可根据属性值的分布情况选择不同方案：

场景1：属性值范围有限（线性复杂度方案） #

如果foo和bar的取值范围不大（比如是0到1000的整数），可以用计数排序实现O(n + k)的线性复杂度（k为属性值的最大范围）。

实现思路 #

1. 统计每个属性值的出现次数，通过前缀和计算出每个值对应的排名起始位置
2. 遍历原数组，直接根据属性值从计数数组中获取排名并赋值
3. 对两个属性重复上述流程

代码示例 #

type Obj = {
  foo: number;
  bar: number;
  rankFoo?: number;
  rankBar?: number;
};

function assignRanks(arr: Obj[]) {
  // 处理rankFoo（降序排名）
  const fooValues = arr.map(item => item.foo);
  const maxFoo = Math.max(...fooValues);
  const countFoo = new Array(maxFoo + 2).fill(0);

  // 统计每个foo值的出现次数
  for (const val of fooValues) {
    countFoo[val]++;
  }

  // 计算前缀和，确定每个值的排名起始索引
  let sum = 0;
  for (let i = maxFoo; i >= 0; i--) {
    const temp = countFoo[i];
    countFoo[i] = sum;
    sum += temp;
  }

  // 给原数组对象赋值rankFoo
  for (const item of arr) {
    item.rankFoo = countFoo[item.foo]++;
  }

  // 同理处理rankBar
  const barValues = arr.map(item => item.bar);
  const maxBar = Math.max(...barValues);
  const countBar = new Array(maxBar + 2).fill(0);

  for (const val of barValues) {
    countBar[val]++;
  }

  sum = 0;
  for (let i = maxBar; i >= 0; i--) {
    const temp = countBar[i];
    countBar[i] = sum;
    sum += temp;
  }

  for (const item of arr) {
    item.rankBar = countBar[item.bar]++;
  }
}

场景2：属性值范围无限制（优化代码冗余） #

如果属性值范围过大，计数排序不适用，可优化代码逻辑减少重复操作，复杂度仍为O(n log n)但更易维护：

实现思路 #

1. 生成带原数组索引的临时数组，避免修改原数组的排序状态
2. 分别按foo和bar排序临时数组，再根据原索引映射回原数组赋值排名

代码示例 #

type Obj = {
  foo: number;
  bar: number;
  rankFoo?: number;
  rankBar?: number;
};

function assignRanks(arr: Obj[]) {
  // 生成包含原索引的临时数组
  const indexedArr = arr.map((item, idx) => ({ ...item, originalIndex: idx }));

  // 按foo降序排序，给原数组赋值rankFoo
  indexedArr.sort((a, b) => b.foo - a.foo);
  indexedArr.forEach((item, rank) => {
    arr[item.originalIndex].rankFoo = rank;
  });

  // 按bar降序排序，给原数组赋值rankBar
  indexedArr.sort((a, b) => b.bar - a.bar);
  indexedArr.forEach((item, rank) => {
    arr[item.originalIndex].rankBar = rank;
  });
}

额外说明 #

• 如果需要相同属性值的元素共享同一排名，可在计数排序的前缀和计算阶段调整逻辑，让相同值的元素使用同一个排名数值
• 计数排序仅适用于属性值为整数且范围可控的场景，否则会导致空间复杂度过高

内容的提问来源于stack exchange，提问作者fenevius-x