本文主要是介绍LeetCode765. 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.length
2 <= n <= 30
n is even.
0 <= row[i] < 2n
All the elements of row are unique.
二、题解
class Solution {
public:int father[31];int nums;int minSwapsCouples(vector<int>& row) {int n = row.size();build(n / 2);for(int i = 0;i < n;i += 2){unions(row[i] / 2,row[i + 1] / 2);}return n / 2 - nums;}void build(int m){for(int i = 0;i < m;i++){father[i] = i;}nums = m;}int find(int x){if(x != father[x]) father[x] = find(father[x]);return father[x];}void unions(int x,int y){int fx = find(x),fy = find(y);if(fx != fy){father[fx] = fy;nums--;}}
};
这篇关于LeetCode765. Couples Holding Hands——并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
