如何高效从DOM元素数组中提取顶级父元素或最末子元素？

你的原始实现思路没问题，但双重forEach循环带来了O(n²)的时间复杂度——当数组里的DOM元素数量较多时（比如上百个），性能会急剧下降。我们可以利用DOM节点的层级特性结合Set的O(1)查找能力，把时间复杂度降到O(n*d)（d是DOM树的深度，通常远小于n），大幅提升效率。

核心优化思路 #

1. 用Set存储元素：替代数组的遍历查找，判断元素是否存在的时间从O(n)降到O(1)。
2. 利用DOM层级链：
   • 筛选顶级父元素：只需检查元素的所有祖先节点是否在数组中，只要有一个在，就不是顶级父。
   • 筛选最末子元素：先标记所有有后代在数组中的元素，剩下的就是没有子元素/后代在数组里的最末子元素。

优化后的完整代码 #

function filterElements(arr, getTopParents = true) {
  const elementSet = new Set(arr);

  if (getTopParents) {
    // 提取顶级父元素：数组中没有任何祖先元素的节点
    return arr.filter(element => {
      let currentParent = element.parentNode;
      while (currentParent) {
        // 只要找到一个父节点在数组里，就不是顶级父
        if (elementSet.has(currentParent)) {
          return false;
        }
        currentParent = currentParent.parentNode;
      }
      return true;
    });
  } else {
    // 提取最末子元素：数组中没有任何后代元素的节点
    const hasDescendantInSet = new Set();
    
    // 遍历所有元素，标记它们在数组中的祖先（这些祖先都有后代在数组里）
    arr.forEach(element => {
      let currentParent = element.parentNode;
      while (currentParent) {
        if (elementSet.has(currentParent)) {
          hasDescendantInSet.add(currentParent);
        }
        currentParent = currentParent.parentNode;
      }
    });

    // 未被标记的元素就是没有后代在数组里的最末子元素
    return arr.filter(element => !hasDescendantInSet.has(element));
  }
}

验证你的示例场景 #

假设你的DOM结构是：

• <div#1>包含<div#2>、<div#4>
• <div#2>包含<div#3>
• <div#5>包含<div#6>
  得到数组arr = [div1, div2, div3, div4, div5, div6]：
• 调用filterElements(arr, true)会返回[div1, div5]（顶级父元素）
• 调用filterElements(arr, false)会返回[div3, div4, div6]（最末子元素）

为什么这个实现更高效？ #

• 原始代码中，每个元素都要和数组里的所有其他元素做一次isDescendant检查，总检查次数是n*(n-1)次。
• 优化后的代码，每个元素最多遍历自己的父链到根节点，总遍历次数是n*d（d是DOM树的深度，一般最多几十层），比O(n²)的复杂度低得多，尤其是当数组元素数量大的时候，性能提升非常明显。

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