力扣1202.交换字符串中的元素

• 并查集

  • multiset：允许重复，并自动排序

•   class Solution {vector<int> vec;public:string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {unordered_map<int,multiset<char>> mp;int n = s.size();//初始化并查集for(int i=0;i<n;i++)vec.emplace_back(i);//联通for(auto it : pairs)vec[find(it[0])] = find(it[1]);//根据并查集存的下标将字母放入哈希表for(int i=0;i<n;i++)mp[find(i)].insert(s[i]);//取出当前下标所在集合ffor(int i=0;i<n;i++){auto f = mp[vec[i]].begin();//将集合中最前面(最小的)赋值当前位置s[i] = *f;mp[vec[i]].erase(f);}return s;}int find(int x){if(vec[x] != x) vec[x] = find(vec[x]);return vec[x];}};