不相交集合元素的数据结构——并查集

不相交集合有两种基本操作:合并(union)和查询(find)。并查集保持了一组不相交的动态集合,每个集合通过一个代表来识别,代表即集合中的某个成员。数组实现Quick Find我们可以直接用数组来存储集合的标识,这样查找操作直接返回对应数组的值即可,复杂度为O(1);而合并操作每次都需要遍历整个数组,复杂度为O(n)。 0 1 2 3 4 5 6 7 8 9 ------------------------------------- ...

子元素 diff 算法的优化

React 的 DiffReact先遍历新数组来找到插入和需要移动的节点,为了避免不必要的移动,react使用了一个哨兵值lastIndex,记录访问过的源数组下标最大值,如果当前元素的下标小于lastIndex,表示原相对位置无法满足需要了需要移动,否则更新lastIndex,这样来最大限度地利用原相对位置。最后遍历一遍旧数组找到需要删除的元素。但这种方式并不是总能得到最优结果。例如:'1234' ➔ '4123'React 并没有将4移到最前面,而是将234都移动一次。因为对新数组的遍...