LeetCode 765 情侣牵手

2021-02-14 2021-02-14 约 1570 字预计阅读 4 分钟

本题的实际解法不难，题目数据范围也很宽容，但是却很好地考查了对具体问题的抽象建模能力。

题目描述

题目大意

2N 个座位上有 N 对情侣，每对情侣不保证相邻、随机分配位置，如果最后需要是他们所有情侣均互相相邻，必须经过一系列交换位置的操作，问对一组特定的输入最少需要多少次交换操作。每个人编号都是 $[0, 2N)$ 内的整数，且各不相同，情侣的编号必定是 $2i$ 和 $2i + 1$，其中 i 表示情侣对的编号取值范围在 $[0, N)$。

输入与输出

示例输入为：

1
2
3
4
5
Input 1:
row = [0,2,1,3]

Intput 2:
row = [3,2,0,1]

row 的长度 $len(row)$ 为偶数，其取值范围是 $[4, 60]$
row 的内容必定是从 0 开始（包括 0）的 $len(row)$ 所有整数的一种全排列

对应输出为：

1
2
3
4
5
Output 1:
1

Output 2:
0

解题思路

本题需要进行一定的假设帮助解题，比如：我们可以假设 2N 个座位是 N 个双人沙发，最后我们需要让每个情侣都在一个双人沙发上就坐。这样的假设不会影响题目的答案，但是能帮我们迅速理清逻辑。最简单直白的情况是，如果一个沙发上已经有了一对配对成功的情侣，那么我们就无需对他们中的任何人进行交换。

并查集

我们可以对未配对的人进行分两种情况讨论。最简单的情况是：如果两个沙发上的人互换了情侣，那么要它们之间只需要一次交换。

我们不关心如何交换，只关心交换的次数。

较为负杂的情况是，多个沙发上的情侣都无法配对，而且欠缺的人组成了一个环，比如下面 3 对情侣的情况：

这样的情况下假设有 k 对情侣成环，其实只要我们找到其中任一个沙发，让这两个人中的一个不变，另一个交换为它的另一半，那么剩余的情侣又变成了一个 k - 1 的环，即设 $T_{k}$ 表示 k 对情侣成环时的交换次数

$$ T_{k} = T_{k-1} + 1 $$

其他，更复杂的情况无非是上面的情况互相组合掺杂。如果任一沙发 x 上有一个人可以和 y 沙发上的人组成情侣，那么我们可以把这两个沙发连接，那么无论 k 对情侣如何相互连接，只要他们同属一个连通分量，都必定有：

$$ T_{k} = k - 1 $$

当然，总共 N 对情侣可能会有多个联通分量，假设有 n 个连通分量，每个连通分量中的情侣对数量为 $N_{i}$，则有如下等式：

$$ \begin{aligned} T_{N} &= \sum_{i=1}^{n} T_{N_{i}}\\ &= \sum_{i=1}^{n} (N_{i} - 1)\\ &= \sum_{i=1}^{n} N_{i} - n\\ &= N - n \end{aligned} $$

显然，我们可以使用并查集解决此问题。实际上我们可以发现因为每对情侣的两人都有十分规律的编号，其实我们借助个人编号得出把每对情侣的编号，只要把个人编号除以 2 即可。那么如果一个沙发上的两个人不是情侣，那么他们计算出的情侣编号也不相同，只要连接这两个编号即可，这代表这两队情侣需要通过交换达到配对。

贪心

并查集不关心交换策略，只从宏观角度计算交换次数，自然也有关心交换策略的解法。本题的解法非常简单，我们每发现一个沙发存在不配对情侣，就任选一个换掉，保证留下的那个人有正确的配对。看起来，我们每次交换操作都需要遍历剩余未配对的人在的沙发，才能确定交换目标所在的沙发，但是其实我们可以实现就遍历一次所有的人，把他们所在的位置和编号进行哈希处理，方便我们根据编号查找位置。这样，每次我们从左到右遍历所有沙发，每个沙发的左侧的人的编号直接可得，那么他的配对目标的编号也可以得到，之后就可以查表得到目标所在的位置。然后，就可以把右侧的人和目标进行位置交换。这样，我们就成功的把暴力扫描的 $O(N^{2})$ 时间复杂度算法，转化为了 $O(N)$ 的贪心算法。

代码

并查集：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    fun minSwapsCouples(row: IntArray): Int {
        val n = row.size / 2
        val unionFind = UnionFind(n)
        for (i in row.indices.step(2)) {
            unionFind.union(row[i] / 2, row[i + 1] / 2)
        }
        return n - unionFind.count
    }
}

class UnionFind(private val total: Int) {

    var count = total
        private set
    private val parent = IntArray(total) { it }
    private val rank = IntArray(total) { 1 }

    fun union(p: Int, q: Int): Boolean {
        val pRoot = find(p)
        val qRoot = find(q)
        if (pRoot == qRoot) return false
        when {
            rank[pRoot] > rank[qRoot] -> parent[qRoot] = pRoot
            rank[pRoot] < rank[qRoot] -> parent[pRoot] = qRoot
            else -> {
                parent[qRoot] = pRoot
                rank[pRoot]++
            }
        }
        count--
        return true
    }

    private fun find(p: Int): Int {
        if (p == parent[p]) return p
        parent[p] = find(parent[p])
        return parent[p]
    }
}

贪心：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    fun minSwapsCouples(row: IntArray): Int {
        val idx = IntArray(row.size)
        for (i in row.indices) {
            idx[row[i]] = i
        }
        var re = 0
        for (i in row.indices.step(2)) {
            val target = row[i] xor 1
            if (target != row[i + 1]) {
                val targetIdx = idx[target]
                idx[row[i + 1]] = targetIdx
                row[targetIdx] = row[i + 1]
                re++
            }
        }
        return re
    }
}

目录

LeetCode 765 情侣牵手

题目描述

题目大意

输入与输出

解题思路

并查集

贪心

代码