-
Notifications
You must be signed in to change notification settings - Fork 417
/
Solution7.java
129 lines (117 loc) · 3.76 KB
/
Solution7.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
/**
* @description:
*
* 给你一个字符串 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 中只含有小写英文字母
*
*/
public class Solution7 {
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
if (pairs.size() <= 1) {
return s;
}
// 第 1 步:将任意交换的结点对输入并查集
int len = s.length();
UnionFind unionFind = new UnionFind(len-1);
for (List<Integer> pair : pairs) {
int index1 = pair.get(0);
int index2 = pair.get(1);
unionFind.union(index1, index2);
}
// 第 2 步:构建映射关系
char[] charArray = s.toCharArray();
// key:连通分量的代表元,value:同一个连通分量的字符集合(保存在一个优先队列中)
Map<Integer, PriorityQueue<Character>> hashMap = new HashMap<>(len);
for (int i = 0; i < len; i++)
int root = unionFind.find(i);
hashMap.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(charArray[i]);
// 第 3 步:重组字符串
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < len; i++) {
int root = unionFind.find(i);
stringBuilder.append(hashMap.get(root).poll());
stringBuilder.append(" ");
}
return stringBuilder.toString();
}
private class UnionFind {
private int[] parent;
/**
* 以 i 为根结点的子树的高度(引入了路径压缩以后该定义并不准确)
*/
private int[] rank;
public UnionFind(int n) {
this.parent = new int[n];
this.rank = new int[n];
for (int i = 0; i < n; i++) {
this.parent[i] = i;
this.rank[i] = 1;
}
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
if (rank[rootX] == rank[rootY]) {
parent[rootX] = rootY;
// 此时以 rootY 为根结点的树的高度仅加了 1
rank[rootY]++;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
// 此时以 rootY 为根结点的树的高度不变
} else {
// 同理,此时以 rootX 为根结点的树的高度不变
parent[rootY] = rootX;
}
}
public int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
}
}