当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--64--交换字符串中的元素（Java
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
(题目来源：力扣（LeetCode）)
示例 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 中只含有小写英文字母
1. 并查集（官方题解）
package com.lxf.bcj;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
public class SmallestStringWithSwaps {
int[] parent;
int[] rank;
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
//获取字符串的char数组
char[] chars = s.toCharArray();
parent=new int[chars.length];//父结点数组
rank=new int[chars.length];//秩数组
for (int i = 0; i < chars.length; i++) {
parent[i]=i;//父结点数组初始化
}
for (List<Integer> pair : pairs) {
//将索引对合并
union(pair.get(0),pair.get(1));
}
//创建一个由父结点为key,存储对应子节点的优先队列为value的hashmap数组
//也就是将有相同父结点的字符存储到一个优先队列中（小根堆）
HashMap<Integer, PriorityQueue<Character>> priorityQueueHashMap= new HashMap<>();
for (int j = 0; j < chars.length; j++) {
//查找当前结点的父结点
int root =find(j);
if(!priorityQueueHashMap.containsKey(root)){//如果没有该key，则创建
PriorityQueue<Character> queue = new PriorityQueue<Character>();
queue.add(chars[j]);
priorityQueueHashMap.put(root,queue);
}else{//已有的话，直接加入
priorityQueueHashMap.get(root).add(chars[j]);
}
//上面7行也可以由下面一行代替，jdk1.8新特性
//priorityQueueHashMap.computeIfAbsent(root,key->new PriorityQueue<>()).offer(chars[j]);
}
//拼接字符串
StringBuilder builder = new StringBuilder();
for (int k = 0; k < chars.length; k++) {
//将当前下标对应父结点的优先队列中的值一一取出来（因为是小根堆，所以会从小到大取）
int root =find(k);
builder.append(priorityQueueHashMap.get(root).poll());
}
return builder.toString();
}
/**
* 合并方法
* @param index1
* @param index2
*/
private void union(int index1, int index2) {
int root1=find(index1);
int root2=find(index2);
if(root1==root2){return;}
if(rank[root1]>rank[root2]){
parent[root2]=root1;
}else if(rank[root1]<rank[root2]){
parent[root1]=root2;
}else{
parent[root2]=root1;
rank[root1]++;
}
}
/**
* 查找父节点方法
* @param index
* @return
*/
public int find(int index){
while(index!=parent[index]){
parent[index]=parent[parent[index]];
index=parent[index];
}
return index;
}
}
