$\textrm{Problem Description : }$$\href{https://leetcode-cn.com/problems/smallest-string-with-swaps/submissions/}{\textrm{LeetCode1202—Smallest String With Swaps}}$

$\textrm{Language: C++}$

$\textrm{Label: Union-Find Disjoint Sets,Group Sorting,Hash}$

$\textrm{Solution:}$

首先简要总结一下题目含义,即有一个字符串$\textrm{S}$,和$\textrm{m}$个二元组$\textrm{(x,y)}$,表示我们可以交换$\textrm{S[x]}$与$\textrm{S[y]}$,每个元组的交换次数不限,交互元组的顺序不限。题目要求以此来构造出$\textrm{S}$可能的最小字典序。易证以下事实$\textrm{:}$

  • 如果$\textrm{S[y] < S[x] and x < y}$,那么$S_{after-swap} < S_{before-swap}$
  • 如果存在元组$\textrm{(x,y),(y,z)}$,那么可以拓展出元组$\textrm{(x,z)}$,也就是说该关系具有自反性,对称性,传递性
  • 在上一条事实下,假设有闭包$\textrm{(a,b,c,d,e,}$……$\textrm{,x,y,z)}$,那么构造最小字典序的步骤应该是
    1. $\textrm{string val = S[a]+S[b]+……+S[z]}$
    2. $\textrm{sort(val)}$
    3. $\textrm{S[a] = val[0],S[b] = val[1],……,S[z] = val[val.size()-1]}$

针对闭包的建立,显然符合并查集的特性,因此简易写了一个并查集,容器命名为$\textrm{a,}$相关函数为$\textrm{find(k)-}$查找$\textrm{k}$的组别,$\textrm{Union(u,v)-}$合并$\textrm{u}$与$\textrm{v}$的组别。之后的分组排序思路其实很多,但每一种似乎有都有一些瑕疵。假设$\textrm{S}$的长度为$\textrm{n}$,那么组别的个数可能远小于$\textrm{n}$,但值却在$\textrm{0-n}$之间。举个例子,假设$\textrm{n=10000,S[0]-S[99]}$的组别都是$\textrm{99}$,$\textrm{S[100]-S[199]}$的组别都是$\textrm{199}$,依次类推,$\textrm{S[9900]-S[9999]}$的组别都是$\textrm{9999}$,那么组别实际上只有$\textrm{100}$个,但是组别的编号值却在$\textrm{99-9999}$不等。开一个$\textrm{10000}$的数组$\textrm{/vector}$浪费空间,而且遍历起来也慢的多,简单的解决方法是离散化 ,排序二分查找或者直接哈希表。本文采用了哈希表的方案,构建一个$\textrm{unordered_map>}$,其中$\textrm{key}$的含义为组别号,$\textrm{val}$是一个$\textrm{string}$与$\textrm{int}$的复合结构。$\textrm{string}$的含义不用多说,是记录下该组别的全部字符,$\textrm{int}$是在重构$\textrm{S}$时的指针,初始化值为$\textrm{0}$。

用一个实例来解释或许更清晰,我们假设$S = “dacbba”$,并查集建立之后的闭包为$(0,2,3)$,$(1,4,5)$,其组别编号分别为$0,1$。于是在哈希表中,应该存在这两项: [$0$->$(dcb,0)$],[$1$->$(aba,0)$]。排序后变为[$0$->$(bcd,0)$], [$1$->$(aab,0)$]。然后我们开始重构字符串:

  1. 首先是$S[0]$,通过$\textrm{find}$查询到其组别号为$0$,然后从哈希表查询$\textrm{key}$=$0$的$\textrm{val}$,得到$(bcd,0)$,于是$S[0]=b$,然后将val更新为$(bcd,1)$,下次再查询到$0$号分组时,将使用$c$字符
  2. 以此类推,$S[1]$的组别号为$1$,得到$(aab,0)$,$S[1] = a$,将$\textrm{val}$更新为$(aab,1)$
  3. $S[2]$的组别为$0$,查询返回$\textrm{val}$为$(bcd,1)$,于是$S[2] = c$,将$\textrm{val}$更新为$(bcd,2)$
  4. $S[3]$的组别为$0$,查询返回$\textrm{val}$为$(bcd,2)$,于是$S[3] = d$,将$\textrm{val}$更新为$(bcd,3)$
  5. $S[4]$的组别为$1$,查询返回$\textrm{val}$为$(aab,1)$,于是$S[4] = a$,将$\textrm{val}$更新为$(bcd,2)$
  6. $S[5]$的组别为$1$,查询返回$\textrm{val}$为$(aab,2)$,于是$S[5] = b$,将$\textrm{val}$更新为$(bcd,3)$

最终得到$S = bacdab$,综述一下流程:

  • 初始化并建立并查集
  • 分组插入哈希表中
  • 排序哈希表每一项的$\textrm{value}$
  • 按序重构字符串

$\textrm{C++ Source Code}$

class Solution {
public:
    int *a;         //并查集数组
    int find(int k) //并查集查找
    {
        if(a[k] != k) a[k] = find(a[k]); //递归更新
        return a[k];
    }
    void Union(int u,int v) //并查集合并
    {
        u = find(u);
        v = find(v);
        a[u] = v;
    }
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        unordered_map<int,pair<string,int>> d; //哈希表
         int n = s.size(),m = pairs.size();
         a = new int [n];
         for(int i = 0;i < n;i++) a[i] = i;   //初始化并查集

         //插入所有元素,完成并查集的建立
         for(int i = 0;i < m;i++) Union(pairs[i][0],pairs[i][1]);

         //将同一组的元素插入哈希表的同一key中
         for(int i = 0;i < n;i++) 
         {
             a[i] = find(i);
             if(!d.count(a[i])) d[a[i]] = make_pair(string(1,s[i]),0);
             else d[a[i]].first += s[i];
         }

         //排序每一组的字符串
         for(auto it = d.begin(); it != d.end();it++)
             sort(it->second.first.begin(),it->second.first.end());

         //按序放置回S字符串中
         for(int i = 0;i < n;i++)
         {
             s[i] = d[a[i]].first[d[a[i]].second];
             d[a[i]].second++;
         }
         return s;
    }
};

分析一下该程序的复杂度,令$S$的长度为$n$,二元组的个数为$m$,因为于是有:

时间复杂度:$O((m+n) \alpha (n) + n \log n)$ ,其中 $\alpha(n)$ 是 Ackermann 函数的反函数,代表了单次查询与合并的复杂度,建立哈希表时进行了$m$次,再构建哈希表时又使用了$n$次,因此为$(m+n) \alpha (n)$,对于排序部分,最坏情况下只有一个闭包,那么复杂度为$n \log n$。最后重构复杂度为$n$,合计得到$O(m \alpha (n) + n \alpha(n) + n \log n + n)$ = $O((m+n) \alpha (n) + n \log n)$
空间复杂度:$O(n)$,并查集与哈希表的空间复杂度均为$n$数量级。

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2021-01-11 22:17}$