Question

1722. 执行交换操作后的最小汉明距离

English Version

题目描述

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。

相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。

在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。

 

示例 1：

输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。

示例 2：

输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。

示例 3：

输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0

 

提示：

• n == source.length == target.length
• 1 <= n <= 105
• 1 <= source[i], target[i] <= 105
• 0 <= allowedSwaps.length <= 105
• allowedSwaps[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi

解法

方法一：并查集 + 哈希表

我们可以将每个下标看作一个节点，每个下标对应的元素看作节点的值，那么给定的 allowedSwaps 中的每个元素 [a_i, b_i] 就表示下标 a_i 和 b_i 之间存在一条边。因此，我们可以使用并查集来维护这些连通分量。

在得到每个连通分量之后，我们再用二维哈希表 $cnt$ 分别统计每个连通分量中每个元素出现的次数，最后对于数组 target 中的每个元素，如果其在对应的连通分量中出现的次数大于 0，则将其出现次数减 1，否则将答案加 1。

时间复杂度 $O(n \times \log n)$ 或 $O(n \times \alpha(n))$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度，而 $\alpha$ 是阿克曼函数的反函数。

class Solution:
  def minimumHammingDistance(
    self, source: List[int], target: List[int], allowedSwaps: List[List[int]]
  ) -> int:
    def find(x: int) -> int:
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    n = len(source)
    p = list(range(n))
    for a, b in allowedSwaps:
      p[find(a)] = find(b)
    cnt = defaultdict(Counter)
    for i, x in enumerate(source):
      j = find(i)
      cnt[j][x] += 1
    ans = 0
    for i, x in enumerate(target):
      j = find(i)
      cnt[j][x] -= 1
      ans += cnt[j][x] < 0
    return ans

class Solution {
  private int[] p;

  public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
    int n = source.length;
    p = new int[n];
    for (int i = 0; i < n; i++) {
      p[i] = i;
    }
    for (int[] a : allowedSwaps) {
      p[find(a[0])] = find(a[1]);
    }
    Map<Integer, Map<Integer, Integer>> cnt = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      int j = find(i);
      cnt.computeIfAbsent(j, k -> new HashMap<>()).merge(source[i], 1, Integer::sum);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int j = find(i);
      Map<Integer, Integer> t = cnt.get(j);
      if (t.merge(target[i], -1, Integer::sum) < 0) {
        ++ans;
      }
    }
    return ans;
  }

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

class Solution {
public:
  int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
    int n = source.size();
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) {
      return x == p[x] ? x : p[x] = find(p[x]);
    };
    for (auto& a : allowedSwaps) {
      p[find(a[0])] = find(a[1]);
    }
    unordered_map<int, unordered_map<int, int>> cnt;
    for (int i = 0; i < n; ++i) {
      ++cnt[find(i)][source[i]];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (--cnt[find(i)][target[i]] < 0) {
        ++ans;
      }
    }
    return ans;
  }
};

func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) (ans int) {
  n := len(source)
  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 _, a := range allowedSwaps {
    p[find(a[0])] = find(a[1])
  }
  cnt := map[int]map[int]int{}
  for i, x := range source {
    j := find(i)
    if cnt[j] == nil {
      cnt[j] = map[int]int{}
    }
    cnt[j][x]++
  }
  for i, x := range target {
    j := find(i)
    cnt[j][x]--
    if cnt[j][x] < 0 {
      ans++
    }
  }
  return
}

function minimumHammingDistance(
  source: number[],
  target: number[],
  allowedSwaps: number[][],
): number {
  const n = source.length;
  const p: number[] = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    if (p[x] !== x) {
      p[x] = find(p[x]);
    }
    return p[x];
  };
  for (const [a, b] of allowedSwaps) {
    p[find(a)] = find(b);
  }
  const cnt: Map<number, Map<number, number>> = new Map();
  for (let i = 0; i < n; ++i) {
    const j = find(i);
    if (!cnt.has(j)) {
      cnt.set(j, new Map());
    }
    const m = cnt.get(j)!;
    m.set(source[i], (m.get(source[i]) ?? 0) + 1);
  }
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    const j = find(i);
    const m = cnt.get(j)!;
    m.set(target[i], (m.get(target[i]) ?? 0) - 1);
    if (m.get(target[i])! < 0) {
      ++ans;
    }
  }
  return ans;
}