LeetCode情侣牵手

841 阅读2分钟

N 对情侣坐在连续排列的 2N 个座位上,想要牵到对方的手。 计算最少交换座位的次数,以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人,让他们站起来交换座位。

人和座位用 0 到 2N-1 的整数表示,情侣们按顺序编号,第一对是 (0, 1),第二对是 (2, 3),以此类推,最后一对是 (2N-2, 2N-1)。

这些情侣的初始座位  row[i] 是由最初始坐在第 i 个座位上的人决定的。

示例 1:

输入: row = [0, 2, 1, 3] 输出: 1 解释: 我们只需要交换row[1]和row[2]的位置即可。 示例 2:

输入: row = [3, 2, 0, 1] 输出: 0 解释: 无需交换座位,所有的情侣都已经可以手牵手了。

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/co…

解题思路:

  1. 循环遍历,每次加2.因为一对情侣2个人一组
  2. 判断单双数,当是单数时,数组当前下标的值-1 等于 下一个下标的数据,表示已经是情侣,或者双数时,数组当前下标的值+1 等于 下一个下标的数据也表示情侣。例如2,3.或者3,2.都是相同的意义。
  3. 当不是情侣时进入sreach方法,重新遍历数组,判断单双,取传入下标的数组的值和当前下标的数据-1相等,那么当前数据比传入的大一个,3 = 4-1.反之也是一样的。例如 2 = 1+1.最后返回找到的对应情侣的下标.
  4. 进行换位,记录次数
public int minSwapsCouples(int[] row) {
        int count = 0;
        // 1
        for (int i = 0; i < row.length; i+=2) {
            // 2
            if(row[i]%2 == 1 && row[i]-1 == row[i+1] || row[i]%2 == 0 && row[i]+1 == row[i+1]) {
                continue;
            } else {
                // 3
                int k = sreach(i, row);
                // 4
                int tmp = row[i+1];
                row[i+1] = row[k];
                row[k] = tmp;
                count++;
            }
        }
        return count;
    }
    
    public int sreach(int k, int[] row) {
        for(int i = 0; i < row.length; i++) {
            if(row[i]%2 == 1) {
                if(row[k] == row[i]-1) {
                    return i;
                }
            } else {
                if(row[k] == row[i]+1) {
                    return i;
                }
            }
        }
        return -1;
    }