题目大意：
交换字符串中的元素
给你一个字符串 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 中只含有小写英文字母
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1202
解题思路分析：
这道题核心是要想到使用Union-Find的方式来解题。简单来说就是分组。pairs中的数字对代表可以两两交换的元素，比如第一位和第二位可以交换，第二位和第五位可以交换，继而可得出，第1，2，5这三位之间可以随意交换，这样我们可以将1，2，5位的三个元素由小到大排列即可。因此，问题就转化为，通过pairs找到所有不连通的集合，然后将各个集合升序排列，最后在组合到一起即是结果。
编码思路如下：
- 先将字符串分成N组。（N为字符串长度）
- 通过pairs找到所有不重合的组。
- 将每一组排序
- 循环字符串，查看当前位属于哪一组，并输出所属组中最小的元素。
编码时，使用union方法进行分组，root方法查找字符串当前位属于哪一组。利用PriorityQueue为组内元素排序。
看下完整实现代码：
int[] union; // 分组用数组。union[i]表示当前位的根下标（即属于哪一组）。
Map<Integer, PriorityQueue> map = new HashMap<>(); // 记录每组中的元素，并排序
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int length = s.length(); // 字符串长度
union = new int[length]; // 初始化分组数组
for(int i=0;i<length;i++){ // 默认当前字符的根为自己
union[i]=i;
}
for(List<Integer> pair : pairs){
// 利用union方法合并组（能连通的部分都归为一组）
union(pair.get(0),pair.get(1));
} // 分组完成
for(int i=0;i<length;i++){ // 循环字符串长度
int root = root(i); // 查看当前位所属哪一组
// 从Map中取出保存当前组的Queue。
PriorityQueue q = map.getOrDefault(root, new PriorityQueue());
// 将当前位对应的字符加入到Queue中。
// 将元素存入PriorityQueue后，会自动排序
q.offer(s.charAt(i));
map.put(root, q); // 保存map
}
StringBuilder res=new StringBuilder(); // 返回值
for(int i=0;i<length;i++){
// 取出当前位所在组中的最小元素，加入返回结果
res.append(map.get(root(i)).poll());
}
return res.toString();
}
// 合并（分组）方法
void union(int index1, int index2){
// 将index1的根连接到index2的根上
union[root(index2)] = root(index1);
}
// 查找根的方法。
int root(int i){
int index = i;
// 值等于下标的元素都为根
// 如果值不等于下标，将值付给下标之后继续查找
while(union[index] != index){
index=union[index];
}
// 更新下标为i的根。（此处跟新为了优化效率）
union[i]=index;
return index; // 返回根
}本算法执行速度为86ms。
Runtime: 86 ms, faster than 42.75% of Java online submissions for Smallest String With Swaps.
Memory Usage: 107.6 MB, less than 100.00% of Java online submissions for Smallest String With Swaps.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1202-smallest-string-with-swaps-解题思路分析/