JavaScript计算Set中位数及Map中位数对应键的高效方法

原生JavaScript没有内置的Set中位数计算函数，但可以自行实现，核心步骤是将Set转为数组后排序，再按中位数规则计算：

function getSetMedian(set) {
  const arr = Array.from(set).sort((a, b) => a - b);
  const length = arr.length;
  
  if (length === 0) return undefined;
  
  const midIndex = Math.floor(length / 2);
  return length % 2 === 1 ? arr[midIndex] : (arr[midIndex - 1] + arr[midIndex]) / 2;
}

说明：

• 通过Array.from(set)将Set转换为数组，再用数值排序规则排序
• 空Set返回undefined，奇数长度取中间元素，偶数长度取中间两元素的平均值

针对元素量较大（如超1000个）的Map，推荐两种方案：

方案一：全排序法（实现简单，中小数据量高效） #

将Map的键值对转为数组后按值排序，直接定位中位数位置的元素并返回其键：

function getMapMedianKey(map) {
  if (map.size === 0) return undefined;
  
  // 转换为键值对数组并按值升序排序
  const sortedEntries = Array.from(map.entries()).sort((a, b) => a[1] - b[1]);
  const length = sortedEntries.length;
  const midIndex = Math.floor(length / 2);
  
  if (length % 2 === 1) {
    // 奇数个元素，返回中间位置的键
    return sortedEntries[midIndex][0];
  } else {
    // 偶数个元素，可返回中间两个元素的任意一个键（此处返回前一个）
    return sortedEntries[midIndex - 1][0];
    // 若需返回两个键，可改为：return [sortedEntries[midIndex - 1][0], sortedEntries[midIndex][0]];
  }
}

方案二：快速选择法（大数据量更高效） #

使用快速选择算法（Quickselect），无需全排序即可定位中位数位置的元素，平均时间复杂度为O(n)，适合百万级以上的大数据量：

// 快速选择核心函数，找到第k小的元素（k从0开始计数）
function quickselect(entries, k) {
  if (entries.length === 1) return entries[0];
  
  // 随机选择基准值，避免最坏情况
  const pivotIndex = Math.floor(Math.random() * entries.length);
  const pivotValue = entries[pivotIndex][1];
  
  const left = []; // 小于基准值的元素
  const mid = [];  // 等于基准值的元素
  const right = [];// 大于基准值的元素
  
  for (const entry of entries) {
    if (entry[1] < pivotValue) {
      left.push(entry);
    } else if (entry[1] === pivotValue) {
      mid.push(entry);
    } else {
      right.push(entry);
    }
  }
  
  if (k < left.length) {
    return quickselect(left, k);
  } else if (k < left.length + mid.length) {
    return mid[0]; // 基准值组内任意元素均可
  } else {
    return quickselect(right, k - left.length - mid.length);
  }
}

function getMapMedianKeyOptimized(map) {
  if (map.size === 0) return undefined;
  
  const entries = Array.from(map.entries());
  const length = entries.length;
  const midIndex = Math.floor(length / 2);
  
  if (length % 2 === 1) {
    const medianEntry = quickselect(entries, midIndex);
    return medianEntry[0];
  } else {
    // 偶数情况需获取中间两个元素，此处返回前一个的键
    const medianEntry = quickselect(entries, midIndex - 1);
    return medianEntry[0];
    // 若需返回两个键，可补充获取midIndex位置的元素后返回数组
  }
}

说明：

• 对于1000个元素的规模，两种方案性能差异极小，全排序法代码更简洁易维护
• 偶数个元素时，中位数通常为中间两元素的平均值，若需返回对应键，可根据业务需求选择其中一个或返回两个键的数组

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