面向对象数组部分重排的高效算法实现问询

给定如下对象数组：

[
  {v: 'a'},
  {v: 'b'},
  {v: 'c', ptr: 'b'},
  {v: 'd', ptr: 'a'},
  {v: 'e'},
]

部分对象包含ptr属性，其值引用某对象的v属性，表示该对象需直接位于被引用对象之前。已知约束：

• 不存在两个对象同时要求前置同一对象
• 无循环引用（如a->b->c->a这类闭环）
• 未被ptr引用的对象位置不受限制，核心只需满足ptr指定的直接前置关系

以下是两种合法重排结果：

[
  {v: 'e'},
  {v: 'd', ptr: 'a'},
  {v: 'a'},
  {v: 'c', ptr: 'b'},
  {v: 'b'},
]

[
  {v: 'c', ptr: 'b'},
  {v: 'b'},
  {v: 'd', ptr: 'a'},
  {v: 'a'},
  {v: 'e'}
]

实际场景中，v和ptr为DOM元素，仅可通过相等性比较判断v与ptr是否匹配。现需实现一种高效的重排算法，且避免无限循环。

算法思路 #

题目给出的约束（无循环、无重复前置）决定了这是一组单向依赖链的处理问题，每个节点最多有一个前置节点。可以通过以下步骤实现高效重排：

1. 建立快速映射：用v（或DOM元素）作为键，构建对象映射表，避免反复遍历数组查找目标对象。
2. 构建依赖链：从每个带ptr的对象出发，顺着依赖关系拼接成完整的前置链（比如d->a、c->b）。
3. 合并结果：将所有依赖链和无依赖的独立节点按任意顺序组合，只要保证链内部的前置顺序正确即可。

代码实现（JS版本） #

function rearrangeItems(items) {
  // 1. 建立v到对应对象的映射，DOM元素可直接作为Map键
  const itemMap = new Map();
  items.forEach(item => itemMap.set(item.v, item));

  // 标记已处理对象，避免重复操作
  const processed = new Set();
  const result = [];

  items.forEach(item => {
    if (processed.has(item)) return;

    if (item.ptr) {
      const chain = [];
      let current = item;
      // 顺着ptr追溯完整依赖链，直到无前置节点或已处理节点
      while (current && !processed.has(current)) {
        chain.unshift(current); // 往前插入，保证链的顺序是前置对象在前
        processed.add(current);
        // DOM元素直接用相等性匹配查找对应对象
        current = itemMap.get(current.ptr);
      }
      result.push(...chain);
    } else {
      // 无依赖的独立节点直接加入结果
      result.push(item);
      processed.add(item);
    }
  });

  return result;
}

// 测试示例
const input = [
  {v: 'a'},
  {v: 'b'},
  {v: 'c', ptr: 'b'},
  {v: 'd', ptr: 'a'},
  {v: 'e'},
];
console.log(rearrangeItems(input));

关键说明 #

• 高效性：时间复杂度为O(n)，每个对象仅被处理一次，映射表查找为O(1)操作。
• 防循环：题目保证无循环引用，因此追溯依赖链时不会陷入无限循环；同时用processed集合标记已处理对象，避免重复处理。
• DOM场景适配：如果v和ptr是DOM元素，Map可直接以DOM元素为键，通过===相等性比较完成匹配，无需额外处理。
• 灵活性：独立节点和不同依赖链的顺序可按需调整（比如示例中的e可放在任意位置），只要链内部符合前置要求即可。

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