难度: Hard
原题连接
内容描述
N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.
The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).
The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.
Example 1:
Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
Example 2:
Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.
Note:
len(row) is even and in the range of [4, 60].
row is guaranteed to be a permutation of 0...len(row)-1.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
证明过程参考Java/C++ O(N) solution using cyclic swapping
以下所有的group指的都是connected component
并查集的思想，by saying "resolving a group", we mean placing the elements at each index contained in the group to their expected positions at the end of the swapping process.
先assume一个论点，size为n的group需要n-1次swap来使得所有的元素放在它应该在的index上
- Base case：如果是一个size 为1的group，我们只需要0次swap就可以让所有的元素放在它应该在的index上
- Induction case：如果是一个size 为k+1的group，那么这个group就是
... --> i --> p --> ... --> j --> q --> ....的形式， 假设i本应该在的位置是j所在的位置，j本应该在的位置是i所在的位置，那么我们将i和j互相换一下，就将这个size为 k+1的group分成了两个disjoint的group。 假设这两个group的size分别为k1和k2，那么我们一直分下去，可以一直分到base case的情况，也就是说size为k1的group需要k1-1次swap，size为k2的grouo 需要k2-1次swap，那么将整个size为k的group全部放到正确的位置上所需要的swap次数就是1 + (k1-1) + (k2-1),也就是k1+k2-1,而其中k1 + k2 = k，所以对于Induction case来说也满足这个论点
证毕
那么对于我们的N对couple来说，其实就是N个node，我们可以把作为input的row看成一个大家庭，其中有几个group我们可以通过并查集或者dfs算出来，设为m， 每做一次swap我们就可以增加一个group，最终我们的目的就是形成N个group，即N对couple，所以我们一共需要N-m次swap
并查集，beats 34.83%
class UnionFind(object):
def __init__(self, n): # 初始化uf数组和组数目
self.count = n
self.uf = [i for i in range(n)]
def find(self, x): # 判断节点所属于的组
while x != self.uf[x]:
self.uf[x] = self.uf[self.uf[x]]
x = self.uf[x]
return self.uf[x]
def union(self, x, y): # 连接两个节点
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return
self.uf[x_root] = y_root
self.count -= 1
class Solution:
def minSwapsCouples(self, row):
"""
:type row: List[int]
:rtype: int
"""
N = len(row) // 2
uf = UnionFind(N)
for i in range(N):
m, n = row[2*i], row[2*i+1]
uf.union(m // 2, n // 2) # 说明这两对couple，即这两个node相互连接
return N - uf.count思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******
看完上面的思路，发现直接用贪心就可以，就是直接从头到尾遍历，没配对成功就立马配对，执行相应swap操作.
因为每一次这样的swap都至少增加了一个connected component，所以肯定是最优的
beats 34.83%
class Solution:
def minSwapsCouples(self, row):
"""
:type row: List[int]
:rtype: int
"""
lookup = {} # people: his idx in row
for idx, ppl in enumerate(row):
lookup[ppl] = idx
res = 0
for i in range(0, len(row), 2):
p1 = row[i]
p2 = p1 + 1 if p1 % 2 == 0 else p1 - 1 # Find p1's couple
if row[i+1] != p2: # p1's couple isn't next to p1
res += 1
s = row[i+1] # stranger
lookup[s], lookup[p2] = lookup[p2], i+1 # swap p2 and cur stranger
row[lookup[s]], row[i+1] = s, p2 # couple in right idx, Stranger is gone
return res