西安有哪些家做网站的公司,邮箱登录入口官网,免费做app的网站有吗,建立一个app需要多少钱n 对情侣坐在连续排列的 2n 个座位上#xff0c;想要牵到对方的手。
人和座位由一个整数数组 row 表示#xff0c;其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号#xff0c;第一对是 (0, 1)#xff0c;第二对是 (2, 3)#xff0c;以此类推#xff0c;最后…n 对情侣坐在连续排列的 2n 个座位上想要牵到对方的手。
人和座位由一个整数数组 row 表示其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号第一对是 (0, 1)第二对是 (2, 3)以此类推最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人让他们站起来交换座位。 示例 1:
输入: row [0,2,1,3]
输出: 1
解释: 只需要交换row[1]和row[2]的位置即可。示例 2:
输入: row [3,2,0,1]
输出: 0
解释: 无需交换座位所有的情侣都已经可以手牵手了。
题解把2n个作为分为n个组每个组最后做一对情侣由题可得 编号/2 相同的人是一对情侣。
如果把一对情侣看成一个点把一个座位看成一条边可以把输入转化成一个图。[0,2,1,3] 转化为情侣[0 1 0 1]。
所以01之间形成一个环。
经过枚举可以发现形成的图是一个或几个环。最终的结果是要变成n-1个自环。
规律
如果每个座位内交换两个人位置那么环的个数不变。
如果不同座位内交换两个人位置那么环的个数加1。
所以只要求一开始的环的个数即可。
使用并查集来求图中环的个数因为图中只有环
初始化每对情侣都指向自己。 class Solution {
public:vectorint p;int find(int x){if(p[x]!x)p[x]find(p[x]);return p[x];}int minSwapsCouples(vectorint row) {int n row.size()/2;for(int i 0;i n;i) p.push_back(i);int cnt 0;for(int i 0;in*2;i2){int a row[i]/2;int b row[i1]/2;if(find(a)!find(b)){p[find(a)]find(b);cnt;}}return cnt;}
};
