765. 情侣牵手

765. 情侣牵手（leetcode,数学思维题）-------------------Java实现

题目表述

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 == row.length
2 <= n <= 30
n 是偶数
0 <= row[i] < 2n
row 中所有元素均无重复

思路

在这里插入图片描述

注意点

ac代码

Java:

class Solution {
    public int minSwapsCouples(int[] row) {
    int[] sit = new int[row.length];
    int result = 0;
    HashSet<Integer> visit = new HashSet<>();
    for(int i=0;i<row.length;i++)
    sit[row[i]] = i;
    for(int i=0;i<row.length;i+=2)
    {

        if(row[i]%2==0&&row[i+1]==row[i]+1||row[i]%2==1&&row[i+1]==row[i]-1||visit.contains(i))
        continue;
        visit.add(i);
        int begin = row[i];
        int time = 0;
        int other = row[i+1];
        while(true)
        {
            
            int target = other%2==0?other+1:other-1; //other的情侣是target
            if(target==begin)
            break;
            else
            time++;
            other = sit[target]%2==0?row[sit[target]+1]:row[sit[target]-1];
            visit.add((sit[target]/2)*2);
        }
        result+=time;
    }
    return result;
    }
}