题目描述
给你一个字符串s,以及该字符串中的一些
「索引对」
数组pairs
,其中pairs[i] =[a, b]表示字符串中的两个索引(编号从 0 开始)。
你可以 任意多次交换 在pairs
中任意一对索引处的字符。
返回在经过若干次交换后,s
可以变成的按字典序最小的字符串。数据范围
1 <=
s.length
<= 10^5
0 <= pairs.length
<= 10^5
0 <=pairs[i][0], pairs[i][1]
< s.length
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
(并查集 + 排序) $O(m + n + nolgn)$
细节:
- 集合合并的时候,加入势力强大的一伙,所以要额外维护每个集合的元素个数
cnt
时间复杂度
- 遍历
pairs
$O(m)$ - 并查集 ~$O(n)$。
- 集合
内部排序
,最坏情况下所有字符都在一个集合中$O(nlog)$
综上 :时间复杂度为$O(m+nlogn)$。
参考文献
wzc : https://www.acwing.com/solution/content/4744/
C++ 代码
class Solution {
public:
vector<int> p, cnt;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
for(int i = 0; i < n; i++) {
p.push_back(i);
cnt.push_back(1);
}
for(auto &pair : pairs){
int a = find(pair[0]), b = find(pair[1]);
if(a != b){
if(cnt[a] < cnt[b]){ // 谁大就加入谁
p[a] = b;
cnt[b] += cnt[a];
}
else{
p[b] = a;
cnt[a] += cnt[b];
}
}
}
vector<vector<char>> conn_char(n);
vector<vector<int>> pos(n);
// 遍历集合 把联通的字符 存入到vector 中 便于排序
for(int i = 0; i < n; i ++){
conn_char[find(i)].push_back(s[i]); // 把每个集合的字符放到一起
pos[find(i)].push_back(i); // 每个集合的中的位置信息
}
for(auto &conn : conn_char) sort(conn.begin(), conn.end());
for(int i = 0; i < n; i ++)
for(int j = 0; j < conn_char[i].size(); j++)
s[pos[i][j]] = conn_char[i][j];
return s;
}
};