Java:使用 Java 8 API 对非连续字符串字符的子集进行排序的更快方法是什么

Question

我有这个 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 方法解决这个问题？如果可能的话？

Answer 1

这是一种方法，可让您以直接的方式使用预先分配大小的额外存储来完成此操作。它假定 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]];
}

Demo.