のJava：Javaの8 API

Question

を使用して、非連続的な文字列の文字のサブセットをソートするより高速な方法は何ですか私は、このJavaコードスニペットposで同じ値がstr内の対応する文字がに属していることを意味し

String str = "acxrabdz"; 
int[] pos = {1, 2, 1, 3, 4, 1, 2, 1}; 

を持っています同じサブセット。私は、各サブセットの文字を辞書順に降順にソートしたい。この例では、サブセット答えはString ans = "zdxrabca";
Iチュなります
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}}
ですstは中間部分集合ではなく最終文字列を取得したい。
どのようにすれば最速のJava 8アプローチを使用して、可能な場合はその場で解決できますか？

Answer 1

これは、事前割り当てサイズの追加ストレージを使用して簡単に行うことができる1つのアプローチです。 pos[]配列内のすべての値が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.