的Java：什麼是中使用Java 8 API

非連續的字符串中的字符子集排序更快的方法我有這樣的Java代碼片斷在pos的Java：什麼是中使用Java 8 API

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

當值相等意味着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";
我舉st想要獲得最終的字符串而不是中間子集。
我該如何解決使用最快的Java 8方法，如果可能的話？

來源

2017-10-10 Titan

根據你的解釋，正確的答案應該是'adcrzxba'。請更新解釋或顯示您當前的算法。另外，非升序=降序:) –

根據dasblinkenlight的評論，@Titan能解釋爲什麼「zdxrabca」是唯一可以接受的答案，「zxbadcra」是錯的？ – Mureinik

@dasblinkenlight wrt「non-ascending」vs「descending」 - 不需要唯一性。「不升序」是不升序的任何次序。字符「acb」以非遞減順序呈現，儘管它們絕對不是按降序排列。 – Mureinik

下面是一種方法，可以讓您以預先分配的大小額外存儲的方式直接執行此操作。它假定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.

來源

2017-10-10 15:59:38 dasblinkenlight

的Java：什麼是中使用Java 8 API

回答

相關問題