主要分为两步:find查找和union合并
其中在find的过程中可以进行路径的压缩,在union的过程中可以利用size数组统计当前树的节点数,从而实现把节点数少的树合并到节点数多的树
每次从后往前等概率抽取一个下标 index(0~i),然后交换该 index 与下标 i 的值
时间复杂度:O(n)
空间复杂度:O(1)
缺点:会打乱原数组,且是从后往前计算,因此不适用于动态变化的数组
当直接使用 int / long 等存储某个元素时,所占用的内存为 4 / 8 字节,而 BitMap 则采用的是一个 bit 位标记某个元素,当对应 bit 位为 1 时表示该元素存在,此时该 bit 位所在的 index 即为该元素的值。
注意:布隆过滤器就是利用了 BitMap 算法思想,但是 BitMap 只能接收 int / long 类型的数据,而布隆过滤器则是通过哈希算法,将输入数据转换为了整数类型