情侣牵手
Couples Holding Hands
题目详情
问题：情侣牵手
考察：数组、贪心、图
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/couples-holding-hands/
There are n couples sitting in 2n seats arranged in a row and want to hold hands.
The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat. 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).
Return 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.
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.
Constraints:
2n == row.length2 <= n <= 30nis even.0 <= row[i] < 2n- All the elements of
roware unique.
解析
思路：把每对情侣看作一个组，当前座位相邻两人若不是一对，就把其中一人的伴侣交换到旁边。也可建图/并查集：每个连通块大小为 m，需要 m-1 次交换。
复杂度：贪心配合位置表 O(n)，空间 O(n)。