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

力扣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]);
            //取出当前下标所在集合f
            for(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];
        }
    };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31