likes
comments
collection
share

[路飞]情侣牵手

作者站长头像
站长
· 阅读数 10

记录 1 道算法题

情侣牵手

有 2n 个情侣,即 n 对。第一对情侣是 [0,1],第二对是 [2,3],最后一对是 [2n - 2, 2n - 1],以每对情侣中第一次出现的那个人的位置为情侣的位置,情侣的位置被拆散了,求最少换多少次可以使他们恢复相邻。

比如: [4,2,0,1,3,5],恢复之后是 [4,5,0,1,3,2]。

有一种直接的解法就是遍历一遍,然后遍历到情侣不是一对,就进行交换,恢复当前的这对情侣,但是不确定是不是最少次数。看题解时看到有一个规律,就是这种遍历一遍的解法也是最小次数的解法,只要不是无意义的交换,按照一对对恢复情侣,先恢复哪一对情侣都是次数最小的。

    function minSwapsCouples (row) {
        const map = {}
        let count = 0
        // 先把坐标存起来,方便找另一个情侣的位置,进行交换
        for(let i = 0; i < row.length; i++) {
            map[row[i]] = i
        }

        for(let i = 0; i < row.length; i+=2) {
            // 2 个 一组进行检查
            // 以第一个为情侣的位置
            // 让这一组的另一个和第一个的情侣进行比较
            const a = row[i]
            const b = row[i + 1]
            const c = another(a)
            if (c !== b) {
                // 如果不同的话就需要交换
                // 把另一半换过来,另一个换走
                const ci = map[c]
                row[i + 1] = c
                row[ci] = b
                // 换完之后需要更新换走的那一个的下标
                map[b] = ci
                count++
            }
        }
        return count
    };

    function another(i) {
        if (i % 2 === 0) {
            return i + 1
        } else {
            return i - 1
        }
    }

也可以用并查集来解题,并查集的话要清楚以什么为单位进行,如果以每个情侣的下标进行合并的话,会非常繁琐,用两个一组的下标会更合适,而且每对情侣的下标进行位运算后刚好能是同一组,其实就是除以 2 向下取整 0 >> 1 === 01 >> 1 === 02 >> 1 === 13 >> 1 === 1,刚好 [0,1] 就是在下标为 0 的第 0 组,[2,3] 在第一组。

然后我们将相邻的情侣所在的组连起来,比如 [0,2],就是将第 0 组和第 1 组连起来。那我们就一定会在某一组停下来,结束连线。比如 [0,2,1,5,4,3],第 0 组连第 1 组,然后第 0 组连第 3 组,第 3 组连第 2 组。题解提到的另一个规律就是,连线形成一个环,然后连线就结束。而所要移动的次数就是这个环内的组的数量 - 1

这个并查集最后我们会得到 k 个根节点,即自己指向自己,其中有一些是不需要恢复的情侣,有一些是通过连接形成的根节点。自己指向自己也可以视为一个环。假设 [0,2,1,5,4,3,6,7],里面有 1 个 3组形成的环和 1 个自己指向自己的环。那次数就是 (3 - 1) + (1 - 1)。如果进行多项式合并会变成 (3 + 1) + (- 1 - 1) --> 4 - 2,刚好就是情侣的组的数量 - 环的数量(并查集根节点数量)。所以结果就出来了。

    function minSwapsCouples(row) {
        const len = row.length
        // 算出多少组情侣,建立并查集
        const n = len / 2
        const parent = Array.from(new Array(n), (_, i) => i)
        let count = 0
        
        // 两个一组遍历
        for (let i = 0; i < len; i += 2) {
          // 将两个所在的组连起来
          const a = row[i] >> 1
          const b = row[i + 1] >> 1
          if (a !== b) {
              parent[find(parent, a)] = parent[find(parent, b)]
          }
        }
        // 计算有多少个环
        for (let i = 0; i < n; i++) {
          if (i === find(parent, i)) count++
        }

        return n - count
    }

    function find(parent, i) {
        if (parent[i] !== i) {
          parent[i] = find(parent, parent[i])
        }

        return parent[i]
    }

结束