LeetCode 1202. 交换字符串中的元素（并查集）

Honoria ·

更新时间:2024-09-20

· 776 次阅读

1. 题目

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以任意多次交换在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1:
输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释： 
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
示例 2：
输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
示例 3：
输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"
提示：
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-string-with-swaps
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

参考：数据结构–并查集（Disjoint-Set）

相关题目：
LeetCode 959. 由斜杠划分区域（并查集）
程序员面试金典 - 面试题 17.07. 婴儿名字（并查集）

把同一个集合中的排序，然后放回去

class dsu
{
public:
	vector f;
	dsu(int n)
	{
		f.resize(n);
		for(int i = 0; i < n; ++i)
			f[i] = i;
	}
	int find(int x)
	{
		if(x == f[x])
			return x;
		return f[x] = find(f[x]);
	}
	void merge(int x, int y)
	{
		int fx = find(x), fy = find(y);
        f[fx] = fy;
	}
};
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector>& pairs) {
    	int n = s.size(), i, fatherid;
    	dsu uni(n);
    	for(i = 0; i < pairs.size(); ++i)
            uni.merge(pairs[i][0],pairs[i][1]);
    	unordered_map<int,multiset> m;
    	for(i = 0; i < n; ++i)
    	{
            // fatherid = uni.f[i];//错误解，使用之前必须先压缩一次
    		fatherid = uni.find(i);
    		m[fatherid].insert(s[i]);
    	}
    	for(i = 0; i < n; ++i)
    	{
    		// fatherid = uni.f[i];//这样也行，上面已经压缩
            fatherid = uni.find(i);
    		s[i] = *m[fatherid].begin();
    		m[fatherid].erase(m[fatherid].begin());
    	}
    	return s;
    }
};

352 ms 46.6 MB