0765. Couples Holding Hands¶
题目信息¶
- 题号:
0765
- 难度:
Hard
- 主题:
排列、成对关系、最少交换
- 原题:
- 重点:
相邻两个座位组成一组;情侣固定为
(0,1)、(2,3)等编号对,一次可交换任意两个人,返回让每组相邻座位都坐一对情侣的最少交换次数
题目重述¶
有 n 对情侣坐在一排 2n 个座位上。数组 row 按座位从左到右给出每个人的编号,且 0 至 2n - 1 每个编号恰好出现一次。情侣关系按编号固定:0 与 1 是一对,2 与 3 是一对,依此类推。
座位 0 与 1、2 与 3 等每两个相邻座位构成一组。一次交换可以任选两个人,让他们互换座位。请返回最少交换次数,使每一组相邻座位中的两个人都是情侣。
2n == row.length,2 <= n <= 30,并且所有 row[i] 都在 [0, 2n - 1] 范围内且互不相同。
自建示例¶
三对情侣形成一个错位环:
输入:row = [5,0,3,4,1,2]
输出:2
解释:可先交换编号 0 与 4,得到 [5,4,3,0,1,2];再交换编号 0 与 2,得到 [5,4,3,2,1,0]。三组座位分别坐着情侣 (4,5)、(2,3)、(0,1)。一次交换无法同时修正这个涉及三对情侣的错位关系。
情侣内部顺序与座位组顺序均不影响结果:
输入:row = [5,4,1,0,3,2]
输出:0
解释:三个座位组分别是 [5,4]、[1,0]、[3,2],对应情侣 (4,5)、(0,1)、(2,3)。情侣可以反向就座,各对情侣所在的座位组也不必按编号排列,因此已经满足要求。