微信建设网站/免费私人网站建设软件

1202. 交换字符串中的元素

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

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

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

思路

• 直接使用并查集，可以交换的索引值组成一个集合，对集合的元素进行排序即可，然后按照位置放回到原数组中。

class Solution {
private:vector<int> f;vector<int> rank;
public://并查集通用代码int find(int x) {if(f[x] == x) {return x;}return f[x] = find(f[x]);}void join(int x, int y) {int f_x = find(x);int f_y = find(y);if(f_x == f_y) {return;}if(rank[f_x] == rank[f_y]) {f[f_x] = f_y;rank[f_y]++;}else if(rank[f_x] < rank[f_y]) {f[f_x] = f_y;}else {f[f_y] = f_x;}}string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {int n = s.size();f.resize(n);rank.resize(n, 1);for(int i = 0; i < n; i++) {f[i] = i;}for(int i = 0; i < pairs.size(); i++) {join(pairs[i][0], pairs[i][1]);}//对数组的元素进行入集合，每个父节点统领一个集合unordered_map<int, vector<int>> mp;for(int i = 0; i < n; i++) {mp[find(i)].push_back(s[i]);} //对每个集合排序for(auto& [x, vec] : mp) {sort(vec.begin(), vec.end(), greater<int>());}//对于数组的位置，查找父节点集合，放入并删除for(int i = 0; i < n; i++) {int father = find(i);s[i] = mp[father].back();mp[father].pop_back();}return s;}
};