0765. Couples Holding Hands ======================================================================================================================== 题目信息 -------- :题号: 0765 :难度: Hard :主题: 排列、成对关系、最少交换 :原题: `LeetCode 0765 `_ :重点: 相邻两个座位组成一组;情侣固定为 ``(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]`` 范围内且互不相同。 自建示例 -------- 三对情侣形成一个错位环: .. code-block:: text 输入: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)。一次交换无法同时修正这个涉及三对情侣的错位关系。 情侣内部顺序与座位组顺序均不影响结果: .. code-block:: text 输入:row = [5,4,1,0,3,2] 输出:0 解释:三个座位组分别是 [5,4]、[1,0]、[3,2],对应情侣 (4,5)、(0,1)、(2,3)。情侣可以反向就座,各对情侣所在的座位组也不必按编号排列,因此已经满足要求。