Leetcode1202-交换字符串中的元素

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

首先简要总结一下题目含义，即有一个字符串$\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)$]。然后我们开始重构字符串:

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

最终得到$S = bacdab$，综述流程:

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

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$数量级。

Author@Kuroko

GitHub@SuperKuroko

LeetCode@kuroko177

Last Modified: 2021-01-11 22:17