Question

765. 情侣牵手

English Version

题目描述

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 中所有元素均无重复

解法

方法一：并查集

我们可以给每一对情侣编号，编号 $0$ 和 $1$ 的人对应情侣 $0$，编号 $2$ 和 $3$ 的人对应情侣 $1$…即编号为 $row[i]$ 对应的情侣编号为 $\lfloor \frac{row[i]}{2} \rfloor$。

如果有 $k$ 对情侣相互之间坐错了位置，也即是说，有 $k$ 对情侣处于一个置换环中，那么他们之间需要经过 $k-1$ 次交换才能都坐到正确的位置上。

为什么？不妨这样考虑，我们先调整一对情侣的位置，使其坐到正确的位置上，那么问题就从 $k$ 对情侣的问题，转换成了 $k-1$ 对情侣的问题。依此类推，最终 $k=1$ 时，交换次数为 $0$。所以，如果 $k$ 对情侣相互之间坐错了位置，那么需要 $k-1$ 次交换。

因此，我们只需要遍历一遍数组，利用并查集找出有多少个置换环，假设有 $x$ 个，每个环的大小（情侣的对数）为 $y_1, y_2, \cdots, y_x$，那么需要交换的次数为 $y_1-1 + y_2-1 + \cdots + y_x-1 = y_1 + y_2 + \cdots + y_x - x = n - x$。

时间复杂度 $O(n \times \alpha(n))$，空间复杂度 $O(n)$。其中 $\alpha(n)$ 为阿克曼函数的反函数，可以认为是一个很小的常数。

class Solution:
  def minSwapsCouples(self, row: List[int]) -> int:
    def find(x: int) -> int:
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    n = len(row) >> 1
    p = list(range(n))
    for i in range(0, len(row), 2):
      a, b = row[i] >> 1, row[i + 1] >> 1
      p[find(a)] = find(b)
    return n - sum(i == find(i) for i in range(n))

class Solution {
  private int[] p;

  public int minSwapsCouples(int[] row) {
    int n = row.length >> 1;
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    for (int i = 0; i < n << 1; i += 2) {
      int a = row[i] >> 1, b = row[i + 1] >> 1;
      p[find(a)] = find(b);
    }
    int ans = n;
    for (int i = 0; i < n; ++i) {
      if (i == find(i)) {
        --ans;
      }
    }
    return ans;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

class Solution {
public:
  int minSwapsCouples(vector<int>& row) {
    int n = row.size() / 2;
    int p[n];
    iota(p, p + n, 0);
    function<int(int)> find = [&](int x) -> int {
      if (p[x] != x) {
        p[x] = find(p[x]);
      }
      return p[x];
    };
    for (int i = 0; i < n << 1; i += 2) {
      int a = row[i] >> 1, b = row[i + 1] >> 1;
      p[find(a)] = find(b);
    }
    int ans = n;
    for (int i = 0; i < n; ++i) {
      ans -= i == find(i);
    }
    return ans;
  }
};

func minSwapsCouples(row []int) int {
  n := len(row) >> 1
  p := make([]int, n)
  for i := range p {
    p[i] = i
  }
  var find func(int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  for i := 0; i < n<<1; i += 2 {
    a, b := row[i]>>1, row[i+1]>>1
    p[find(a)] = find(b)
  }
  ans := n
  for i := range p {
    if find(i) == i {
      ans--
    }
  }
  return ans
}

function minSwapsCouples(row: number[]): number {
  const n = row.length >> 1;
  const p: number[] = Array(n)
    .fill(0)
    .map((_, i) => i);
  const find = (x: number): number => {
    if (p[x] !== x) {
      p[x] = find(p[x]);
    }
    return p[x];
  };
  for (let i = 0; i < n << 1; i += 2) {
    const a = row[i] >> 1;
    const b = row[i + 1] >> 1;
    p[find(a)] = find(b);
  }
  let ans = n;
  for (let i = 0; i < n; ++i) {
    if (i === find(i)) {
      --ans;
    }
  }
  return ans;
}

public class Solution {
  private int[] p;

  public int MinSwapsCouples(int[] row) {
    int n = row.Length >> 1;
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    for (int i = 0; i < n << 1; i += 2) {
      int a = row[i] >> 1;
      int b = row[i + 1] >> 1;
      p[find(a)] = find(b);
    }
    int ans = n;
    for (int i = 0; i < n; ++i) {
      if (p[i] == i) {
        --ans;
      }
    }
    return ans;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}