Medium

题目描述

给你两个长度为 n 的整数数组 source 和 target。你还有一个数组 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 和 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 <= 10^5
  • 1 <= source[i], target[i] <= 10^5
  • 0 <= allowedSwaps.length <= 10^5
  • allowedSwaps[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi

解题思路

这道题的核心思路是将可以相互交换的位置看作一个连通分量，在每个连通分量内部，我们可以任意重新排列元素。

解题步骤：

  1. 构建图结构：将数组的每个索引看作图的节点，allowedSwaps中的每对索引构成一条边。这样形成了一个无向图。

  2. 寻找连通分量：使用并查集（Union-Find）或深度优先搜索（DFS）找出所有连通分量。在同一个连通分量中的位置可以通过一系列交换操作达到任意排列。

  3. 计算最优匹配：对于每个连通分量，统计source和target在这些位置上的元素频次。我们可以让source中的元素尽可能多地匹配target中的对应元素。

  4. 计算汉明距离：对于每个连通分量，汉明距离的贡献等于该分量的大小减去可以匹配的元素对数。

算法优化：使用并查集来高效地找到连通分量，然后用哈希表统计每个分量中元素的频次，计算最大可能的匹配数。

这种方法的时间复杂度主要由并查集操作和频次统计决定，是一个相对高效的解决方案。

代码实现

class Solution {
public:
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
    
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // Build union-find structure
        for (auto& swap : allowedSwaps) {
            unite(swap[0], swap[1]);
        }
        
        // Group indices by their root
        unordered_map<int, vector<int>> groups;
        for (int i = 0; i < n; i++) {
            groups[find(i)].push_back(i);
        }
        
        int hamming = 0;
        for (auto& [root, indices] : groups) {
            unordered_map<int, int> sourceCount, targetCount;
            
            // Count frequencies in current group
            for (int idx : indices) {
                sourceCount[source[idx]]++;
                targetCount[target[idx]]++;
            }
            
            // Calculate matches
            int matches = 0;
            for (auto& [val, count] : sourceCount) {
                matches += min(count, targetCount[val]);
            }
            
            hamming += indices.size() - matches;
        }
        
        return hamming;
    }
};

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n = len(source)
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        # Build union-find structure
        for a, b in allowedSwaps:
            unite(a, b)
        
        # Group indices by their root
        groups = {}
        for i in range(n):
            root = find(i)
            if root not in groups:
                groups[root] = []
            groups[root].append(i)
        
        hamming = 0
        for indices in groups.values():
            from collections import Counter
            source_count = Counter(source[i] for i in indices)
            target_count = Counter(target[i] for i in indices)
            
            # Calculate matches
            matches = 0
            for val, count in source_count.items():
                matches += min(count, target_count[val])
            
            hamming += len(indices) - matches
        
        return hamming

public class Solution {
    private int[] parent;
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    private void Unite(int x, int y) {
        int px = Find(x), py = Find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
    
    public int MinimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.Length;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // Build union-find structure
        foreach (var swap in allowedSwaps) {
            Unite(swap[0], swap[1]);
        }
        
        // Group indices by their root
        var groups = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            int root = Find(i);
            if (!groups.ContainsKey(root)) {
                groups[root] = new List<int>();
            }
            groups[root].Add(i);
        }
        
        int hamming = 0;
        foreach (var indices in groups.Values) {
            var sourceCount = new Dictionary<int, int>();
            var targetCount = new Dictionary<int, int>();
            
            // Count frequencies in current group
            foreach (int idx in indices) {
                sourceCount[source[idx]] = sourceCount.GetValueOrDefault(source[idx], 0) + 1;
                targetCount[target[idx]] = targetCount.GetValueOrDefault(target[idx], 0) + 1;
            }
            
            // Calculate matches
            int matches = 0;
            foreach (var kvp in sourceCount) {
                int val = kvp.Key, count = kvp.Value;
                matches += Math.Min(count, targetCount.GetValueOrDefault(val, 0));
            }
            
            hamming += indices.Count - matches;
        }
        
        return hamming;
    }
}

var minimumHammingDistance = function(source, target, allowedSwaps) {
    const n = source.length;
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function unite(x, y) {
        const px = find(x), py = find(y);
        if (px !== py) {
            parent[px] = py;
        }
    }
    
    // Build union-find structure
    for (const [a, b] of allowedSwaps) {
        unite(a, b);
    }
    
    // Group indices by their root
    const groups = new Map();
    for (let i = 0; i < n; i++) {
        const root = find(i);
        if (!groups.has(root)) {
            groups.set(root, []);
        }
        groups.get(root).push(i);
    }
    
    let hamming = 0;
    for (const indices of groups.values()) {
        const sourceCount = new Map();
        const targetCount = new Map();
        
        // Count frequencies in current group
        for (const idx of indices) {
            sourceCount.set(source[idx], (sourceCount.get(source[idx]) || 0) + 1);
            targetCount.set(target[idx], (targetCount.get(target[idx]) || 0) + 1);
        }
        
        // Calculate matches
        let matches = 0;
        for (const [val, count] of sourceCount) {
            matches += Math.min(count, targetCount.get(val) || 0);
        }
        
        hamming += indices.length - matches;
    }
    
    return hamming;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
并查集构建O(m·α(n))O(n)
分组统计O(n)O(n)
频次计算O(n)O(n)
总体O(m·α(n) + n)O(n)

其中 n 是数组长度，m 是 allowedSwaps 的长度，α(n) 是反阿克曼函数（实际应用中可视为常数）。

相关题目