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…
解题思路:
- 循环遍历,每次加2.因为一对情侣2个人一组
- 判断单双数,当是单数时,数组当前下标的值-1 等于 下一个下标的数据,表示已经是情侣,或者双数时,数组当前下标的值+1 等于 下一个下标的数据也表示情侣。例如2,3.或者3,2.都是相同的意义。
- 当不是情侣时进入sreach方法,重新遍历数组,判断单双,取传入下标的数组的值和当前下标的数据-1相等,那么当前数据比传入的大一个,3 = 4-1.反之也是一样的。例如 2 = 1+1.最后返回找到的对应情侣的下标.
- 进行换位,记录次数
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;
}