Question

1722. Minimize Hamming Distance After Swap Operations

中文文档

Description

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).

Return _the minimum Hamming distance of _source_ and _target_ after performing any amount of swap operations on array _source_._

 

Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: source can be transformed the following way:
- Swap indices 0 and 1: source = [2,1,3,4]
- Swap indices 2 and 3: source = [2,1,4,3]
The Hamming distance of source and target is 1 as they differ in 1 position: index 3.

Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Explanation: There are no allowed swaps.
The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.

Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0

 

Constraints:

• 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

Solutions

Solution 1: Union-Find + Hash Table

We can consider each index as a node, and the element corresponding to each index as the value of the node. Then each element [a_i, b_i] in the given allowedSwaps represents an edge between index a_i and b_i. Therefore, we can use a union-find set to maintain these connected components.

After obtaining each connected component, we use a two-dimensional hash table $cnt$ to count the number of occurrences of each element in each connected component. Finally, for each element in the array target, if its occurrence count in the corresponding connected component is greater than 0, we decrease its count by 1, otherwise, we increase the answer by 1.

The time complexity is $O(n \times \log n)$ or $O(n \times \alpha(n))$, and the space complexity is $O(n)$. Here, $n$ is the length of the array, and $\alpha$ is the inverse Ackermann function.

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;
}