如何用函数式方法在JavaScript中将稀疏数组转为稠密数组？

问题场景 #

给定按id排序的稀疏数组和目标稠密数组大小：

const sparseArray = [
  {"id":3, "value":"banana"},
  {"id":7, "value":"coconut"}
];
const denseArraySize=10;

需要转换为如下稠密数组：

const denseArray = [
  {"id":0, "value":undefined},
  {"id":1, "value":undefined},
  {"id":2, "value":undefined},
  {"id":3, "value":"banana"},
  {"id":4, "value":undefined},
  {"id":5, "value":undefined},
  {"id":6, "value":undefined},
  {"id":7, "value":"coconut"},
  {"id":8, "value":undefined},
  {"id":9, "value":undefined}
];

此前在C++中可用ranges::set_union()实现线性时间的惰性转换，在SQL中通过LEFT JOIN和COALESCE实现，以下是JavaScript中的函数式实现方案：

实现方案 #

1. 直观函数式实现（适合小数据量） #

利用Array.from生成目标长度的数组，结合find匹配对应id的元素，逻辑简单直观：

const sparseToDense = (sparse, size) => 
  Array.from({ length: size }, (_, idx) => {
    const matchedItem = sparse.find(item => item.id === idx);
    return { id: idx, value: matchedItem?.value };
  });

// 调用示例
const denseArray = sparseToDense(sparseArray, denseArraySize);

注：该方法时间复杂度为O(size × sparse.length)，数据量较大时性能会下降。

2. 线性时间函数式实现（推荐） #

利用稀疏数组已按id排序的特性，采用双指针思路遍历，实现O(size + sparse.length)的线性时间复杂度，和你之前用C++的ranges::set_union()逻辑一致：

const sparseToDenseLinear = (sparse, size) => {
  let sparsePtr = 0;
  return Array.from({ length: size }, (_, idx) => {
    if (sparsePtr < sparse.length && sparse[sparsePtr].id === idx) {
      return { ...sparse[sparsePtr++] };
    }
    return { id: idx, value: undefined };
  });
};

// 调用示例
const denseArray = sparseToDenseLinear(sparseArray, denseArraySize);

3. 基于Reduce的纯函数式实现 #

如果偏好更纯粹的函数式风格，可通过reduce封装双指针逻辑：

const sparseToDenseFunctional = (sparse, size) => {
  return Array.from({ length: size }, (_, idx) => idx)
    .reduce(({ result, ptr }, currentId) => {
      if (ptr < sparse.length && sparse[ptr].id === currentId) {
        return {
          result: [...result, { ...sparse[ptr] }],
          ptr: ptr + 1
        };
      }
      return {
        result: [...result, { id: currentId, value: undefined }],
        ptr
      };
    }, { result: [], ptr: 0 })
    .result;
};

// 调用示例
const denseArray = sparseToDenseFunctional(sparseArray, denseArraySize);

内容的提问来源于stack exchange，提问作者Ludovic Aubert