并查集的妙用——Leetcode 1202
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中
pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 1:
输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
示例 2：
输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
示例 3：
输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"
提示：
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母
这个题的思路是很容易想到的，pairs把下标分成若干组，其中每一组内的下标，元素是可以以任意顺序排列的。那么只需要把这些下标分成若干组，在把每组内的下标对应的元素升序排列，就可以得到答案了。很显然，想要找到互相有联系的下标，就要用到并查集。 第一次打出来的代码如下：
class Solution
{
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs)
{
unordered_map<int, int> hash;
for (int i = 0; i < pairs.size(); ++i)
{
if (findUnion(pairs[i][0], hash) !=
findUnion(pairs[i][1], hash))
{
hash[findUnion(hash[pairs[i][1]], hash)] =
findUnion(pairs[i][0], hash);
}
}
vector<bool> flags(s.size(), 1);
int cur_union = -1;
for (bool b = 0; ; b = 0, cur_union = -1)
{
string str;
vector<int> idx;
for (int i = 0; i < s.size(); ++i)
{
if (flags[i]) //当前字符s[i]可以交换
{
if (cur_union == -1) //当前还未有联盟
{
flags[i] = 0; //s[i]参与交换
cur_union = findUnion(i, hash); //确定联盟
idx.push_back(i); //i放入idx
str += s[i]; //s[i]放入str
b = 1; //标记有参与交换
}
else //当前已有联盟
{
if (cur_union == findUnion(i, hash))
//s[i]属于当前联盟
{
flags[i] = 0;
idx.push_back(i);
str += s[i];
}
}
}
}
if (!b) { break; }
sort(str.begin(), str.end());
for (int i = 0; i < str.size(); ++i)
{
s[idx[i]] = str[i];
}
}
return s;
}
int findUnion(int i, unordered_map<int, int>& hash)
{
if (hash.find(i) == hash.end())
//map和unordered_map的key在未插入的情况下，访问这个key，会自
//动把key的value赋值为0
{
return hash[i] = i;
}
if (hash[i] != i)
{
hash[i] = findUnion(hash[i], hash);
}
return hash[i];
}
};
这份代码并不是很优秀的，主要有以下几个问题：
· map和unordered_map的key在未插入的情况下，访问这个key，会自动把key的value赋值为0，因此findUnion函数要先判断是否存在key；
· 所有下标分组后，对每个组的下标对应的元素进行排序的过程过于繁琐
因此，代码可以做以下改进。首先，用vector代替unordered_map，作为并查集；其次可以对分好组的下标对应的元素，用代码所示的方法进行排序：
class Solution
{
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs)
{
int n = s.size();
for (int i = 0; i < n; ++i)
{
parent.push_back(i);
}
for (auto& it : pairs)
{
int px = findUnion(it[0]), py = findUnion(it[1]);
if (px != py)
{
parent[px] = py;
}
}
unordered_map<int, vector<int> > mem;
//key是“盟主”, value是个向量，保存“联盟”的所有下标对应的字符
for (int i = 0; i < n; ++i)
{
mem[findUnion(i)].push_back(s[i]);
}
for (auto& it : mem)
{
sort(it.second.begin(), it.second.end(), greater<int>());
//降序排序，方便到时候先取出最小的
}
string res;
for (int i = 0; i < n; ++i)
{
int x = findUnion(i); //找到“盟主”
res.push_back(mem[x].back()); //拿出“联盟”中最小的字符
mem[x].pop_back(); //删除这个字符
}
return res;
}
int findUnion(int i)
{
if (parent[i] != i)
{
parent[i] = findUnion(parent[i]);
}
return parent[i];
}
vector<int> parent;
};
更多精彩内容，敬请期待。
