JS多维字符串数组合并去重并保留元素相对顺序的算法实现

• 遍历所有子数组，为同一子数组内相邻的前后元素建立优先级约束：前序元素的优先级高于后序元素，最终输出时前序元素必须排在后序元素之前
• 用有向无环图存储优先级关系，同时统计每个元素的入度
• 采用拓扑排序生成最终结果，不存在优先级约束的元素排序无要求，刚好符合需求中foe和baz的顺序可自由调整的规则

JavaScript 版本 #

function processMultiArray(arr) {
  const graph = new Map();
  const inDegree = new Map();

  // 初始化图结构和入度统计表
  arr.forEach(subArr => {
    subArr.forEach(item => {
      if (!graph.has(item)) {
        graph.set(item, new Set());
        inDegree.set(item, 0);
      }
    });
  });

  // 构建优先级边，避免重复添加导致入度统计错误
  arr.forEach(subArr => {
    for (let i = 0; i < subArr.length - 1; i++) {
      const prev = subArr[i];
      const next = subArr[i + 1];
      if (!graph.get(prev).has(next)) {
        graph.get(prev).add(next);
        inDegree.set(next, inDegree.get(next) + 1);
      }
    }
  });

  // 拓扑排序生成结果
  const queue = [];
  inDegree.forEach((degree, item) => {
    if (degree === 0) queue.push(item);
  });

  const result = [];
  while (queue.length) {
    const current = queue.shift();
    result.push(current);
    graph.get(current).forEach(neighbor => {
      inDegree.set(neighbor, inDegree.get(neighbor) - 1);
      if (inDegree.get(neighbor) === 0) {
        queue.push(neighbor);
      }
    });
  }

  return result;
}

// 测试用例
const myMultiDimensionalArray = [
  ['foo', 'bar'],
  ['foo', 'baz', 'bar'],
  ['foe', 'bar'],
];
const myProcessedArray = processMultiArray(myMultiDimensionalArray);
console.log(myProcessedArray);
// 输出 ['foo', 'foe', 'baz', 'bar'] 或 ['foo', 'baz', 'foe', 'bar'] 均符合预期

TypeScript 版本 #

function processMultiArray(arr: string[][]): string[] {
  const graph = new Map<string, Set<string>>();
  const inDegree = new Map<string, number>();

  // 初始化图结构和入度统计表
  arr.forEach(subArr => {
    subArr.forEach(item => {
      if (!graph.has(item)) {
        graph.set(item, new Set());
        inDegree.set(item, 0);
      }
    });
  });

  // 构建优先级边
  arr.forEach(subArr => {
    for (let i = 0; i < subArr.length - 1; i++) {
      const prev = subArr[i];
      const next = subArr[i + 1];
      if (!graph.get(prev)!.has(next)) {
        graph.get(prev)!.add(next);
        inDegree.set(next, inDegree.get(next)! + 1);
      }
    }
  });

  // 拓扑排序
  const queue: string[] = [];
  inDegree.forEach((degree, item) => {
    if (degree === 0) queue.push(item);
  });

  const result: string[] = [];
  while (queue.length) {
    const current = queue.shift()!;
    result.push(current);
    graph.get(current)!.forEach(neighbor => {
      inDegree.set(neighbor, inDegree.get(neighbor)! - 1);
      if (inDegree.get(neighbor) === 0) {
        queue.push(neighbor);
      }
    });
  }

  return result;
}

如果不需要严格遵守子数组内的优先级约束，仅需要扁平化后按全局首次出现顺序去重，可以使用以下极简方案，注意该方案不符合当前需求的优先级排序要求：

const myProcessedArray = [...new Set(myMultiDimensionalArray.flat())];

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