我有这个 Java 代码片段
String str = "acxrabdz";
int[] pos = {1, 2, 1, 3, 4, 1, 2, 1};
pos
中的相等值表示str
中对应的字符属于同一个子集。我想按字典降序对每个子集中的字符进行排序。在示例中,子集是
1: {{a, pos: 0}, {x, pos: 2}, {b, pos: 5}, {z, pos: 7}}
2: {{c, pos: 1}, {d, pos: 6}}
3: {{r, pos: 3}}
4: {{a, pos: 4}}
和有序子集
1: {{z, pos: 0}, {x, pos: 2}, {b, pos: 5}, {a, pos: 7}}
2: {{d, pos: 1}, {c, pos: 6}}
3: {{r, pos: 3}}
4: {{a, pos: 4}}
答案将是 String ans = "zdxrabca";
我只想获取最终字符串而不是中间子集。
我如何使用最快的 Java 8 方法解决这个问题?如果可能的话?
最佳答案
这是一种方法,可让您以直接的方式使用预先分配大小的额外存储来完成此操作。它假定 pos[]
数组中的所有值都在从 1 到 N 的范围内(含 1 和 N),其中 N 是 str
中的字符数。
算法非常简单。查看评论以了解正在发生的事情。
char[] str = "acxrabdz".toCharArray();
int[] pos = {1, 2, 1, 3, 4, 1, 2, 1};
int[] len = new int[pos.length];
// Count how many characters are in each group
for (int n : pos) {
len[n-1]++;
}
// Pre-allocate space for each group of characters
char[][] tmp = new char[pos.length][];
for (int i = 0 ; i != pos.length ; i++) {
if (len[i] != 0) {
tmp[i] = new char[len[i]];
}
}
// Scatter characters from the string into their group arrays
int[] tpos = new int[pos.length];
for (int i = 0 ; i != pos.length ; i++) {
int p = pos[i]-1;
tmp[p][tpos[p]++] = str[i];
}
// Sort each individual group in ascending order
for (int i = 0 ; i != pos.length ; i++) {
if (tmp[i] != null) {
Arrays.sort(tmp[i]);
}
}
// Put characters back into the string starting at the back
for (int i = 0 ; i != pos.length ; i++) {
int p = pos[i]-1;
str[i] = tmp[p][--tpos[p]];
}
关于Java:使用 Java 8 API 对非连续字符串字符的子集进行排序的更快方法是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46668950/