765_情侣牵手

难度：困难

题目

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。

返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

示例

示例一：

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

示例二：

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

提示

  • 2n == row.length
  • 2 <= n <= 30
  • n 是偶数
  • 0 <= row[i] < 2n
  • row 中所有元素均无重复

解题

用贪心算法，从前往后处理，以两格为一步。先检查 0 的右边是不是情侣，如果不是，就讲 0 号位置的情侣换到 1，然后检查 2 号位置的右边是不是情侣。

在求某个数字 x 的情侣时，可以用 x^1:

  • 当 x 是偶数，则二进制末尾是 0 ，x^1将末尾改成了 1，则 x 的对象是 x+1
  • 当 x 是奇数，则二进制末尾是 1， x^1将末尾改成了 0，则 x 的对象是 x-1

可以用数组 cache 存储每个人对应的位置存储起来

1
2
3
4
int[] cache = new int[n];
for (int i = 0; i < n; i++) {
  cache[row[i]]=i;
}

具体流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int i = 0; i < n - 1; i+=2) {
  // b 为 a 的情侣
  int a = row[i], b=a^1;
  // 当 a 的右边不是 b 时
  if (row[i+1]!=b){
    // 将 b 的位置换到 a 的右边
    int src = i+1, target = cache[b];
    // 更新 cache
    cache[row[target]] = src;
    cache[row[src]] = target;
    // 交换位置
    swap(row,src,target);
    // 记录操作次数
    ans++;
  }
}

结合起来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int minSwapsCouples(int[] row){
  int n = row.length;
  int ans = 0;
  int[] cache = new int[n];
  for (int i = 0; i < n; i++) {
    cache[row[i]]=i;
  }
  for (int i = 0; i < n - 1; i+=2) {
    int a = row[i], b=a^1;
    if (row[i+1]!=b){
      int src = i+1, target = cache[b];
      cache[row[target]] = src;
      cache[row[src]] = target;
      swap(row,src,target);
      ans++;
    }
  }
  return ans;
}

public void swap(int[] nums, int a, int b){
  int c = nums[a];
  nums[a] = nums[b];
  nums[b] = c;
}