[路飞]情侣牵手

记录 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 === 0，1 >> 1 === 0，2 >> 1 === 1，3 >> 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]
    }

结束