[路飞]情侣牵手
记录 1 道算法题
情侣牵手
有 2n 个情侣,即 n 对。第一对情侣是 [0,1],第二对是 [2,3],最后一对是 [2n - 2, 2n - 1],以每对情侣中第一次出现的那个人的位置为情侣的位置,情侣的位置被拆散了,求最少换多少次可以使他们恢复相邻。
比如: [4,2,0,1,3,5],恢复之后是 [4,5,0,1,3,2]。
有一种直接的解法就是遍历一遍,然后遍历到情侣不是一对,就进行交换,恢复当前的这对情侣,但是不确定是不是最少次数。看题解时看到有一个规律,就是这种遍历一遍的解法也是最小次数的解法,只要不是无意义的交换,按照一对对恢复情侣,先恢复哪一对情侣都是次数最小的。
function minSwapsCouples (row) {
const map = {}
let count = 0
// 先把坐标存起来,方便找另一个情侣的位置,进行交换
for(let i = 0; i < row.length; i++) {
map[row[i]] = i
}
for(let i = 0; i < row.length; i+=2) {
// 2 个 一组进行检查
// 以第一个为情侣的位置
// 让这一组的另一个和第一个的情侣进行比较
const a = row[i]
const b = row[i + 1]
const c = another(a)
if (c !== b) {
// 如果不同的话就需要交换
// 把另一半换过来,另一个换走
const ci = map[c]
row[i + 1] = c
row[ci] = b
// 换完之后需要更新换走的那一个的下标
map[b] = ci
count++
}
}
return count
};
function another(i) {
if (i % 2 === 0) {
return i + 1
} else {
return i - 1
}
}
也可以用并查集来解题,并查集的话要清楚以什么为单位进行,如果以每个情侣的下标进行合并的话,会非常繁琐,用两个一组的下标会更合适,而且每对情侣的下标进行位运算后刚好能是同一组,其实就是除以 2 向下取整 0 >> 1 === 0
,1 >> 1 === 0
,2 >> 1 === 1
,3 >> 1 === 1
,刚好 [0,1] 就是在下标为 0 的第 0 组,[2,3] 在第一组。
然后我们将相邻的情侣所在的组连起来,比如 [0,2],就是将第 0 组和第 1 组连起来。那我们就一定会在某一组停下来,结束连线。比如 [0,2,1,5,4,3],第 0 组连第 1 组,然后第 0 组连第 3 组,第 3 组连第 2 组。题解提到的另一个规律就是,连线形成一个环,然后连线就结束。而所要移动的次数就是这个环内的组的数量 - 1
。
这个并查集最后我们会得到 k 个根节点,即自己指向自己,其中有一些是不需要恢复的情侣,有一些是通过连接形成的根节点。自己指向自己也可以视为一个环。假设 [0,2,1,5,4,3,6,7],里面有 1 个 3组形成的环和 1 个自己指向自己的环。那次数就是 (3 - 1) + (1 - 1)。如果进行多项式合并会变成 (3 + 1) + (- 1 - 1) --> 4 - 2,刚好就是情侣的组的数量 - 环的数量(并查集根节点数量)
。所以结果就出来了。
function minSwapsCouples(row) {
const len = row.length
// 算出多少组情侣,建立并查集
const n = len / 2
const parent = Array.from(new Array(n), (_, i) => i)
let count = 0
// 两个一组遍历
for (let i = 0; i < len; i += 2) {
// 将两个所在的组连起来
const a = row[i] >> 1
const b = row[i + 1] >> 1
if (a !== b) {
parent[find(parent, a)] = parent[find(parent, b)]
}
}
// 计算有多少个环
for (let i = 0; i < n; i++) {
if (i === find(parent, i)) count++
}
return n - count
}
function find(parent, i) {
if (parent[i] !== i) {
parent[i] = find(parent, parent[i])
}
return parent[i]
}
结束
转载自:https://juejin.cn/post/7062022021298782215