题目
描述
$n$ 对情侣坐在连续排列的 $2n$ 个座位上, 想要牵到对方的手.
人和座位由一个整数数组 $row$ 表示, 其中 $row[i]$ 是坐在第 $i$ 个座位上的人的 $\text{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 == row.length$
- $2 \le n \le 30$
- $n$ 是偶数
- $0 \le row[i] < 2n$
- $row$ 中所有元素均无重复
我的想法
我一点点思路都没有, 不知道混坐之后是一个什么情况. 最后发现解答中是通过强连通分量做的, 然后瞬时就理解了, 那是具体的怎么求连通分量, 以及连通分量中的元素个数暂时不知道. 并查集这种做法我知道, 但是深度优先和广度优先不清楚怎么做.
另外其他网友提出可以用位运算和贪心来做, 我可以了解, 但是毕竟不是常规思路, 了解一下也行.
文章评论