如何排序的ASCII字符線性時間和恆定的空間

-3

A string of ascii characters, in sorted order of their ascii values. You can overwrite the existing array 

Aim for linear time and constant additional space 

Use the fact that ascii has only 256 unique characters

我可以通過遞增細胞的計數完成線性時間複雜度，與細胞[I ] +256，然後做一個（cell [i]/256）+1，以獲得計數。然後，也許，打印出字符串。但這仍然是O(n)空間，因爲我無法將輸出保存在與輸入相同的數組中。

此外，由於該方法的原型是，

public String sortCharacters(String str) 
{ 

}

由於字符串是不可變Java中，是不是這個問題不可能解決的？

來源

2017-04-11 saltandwater

它看起來像這個問題本來是約一個char []，有人將其改爲字符串，但他們並沒有將所有記錄到「陣列「 –

請仔細看看** Radix Sort ** https://en.wikipedia.org/wiki/Radix_sort –

是的，'String'是不可變的，但是'StringBuilder'，'StringBuffer'，'char []'不是 –

使用只有256個字符的事實。爲256個字符創建一個哈希映射。由於數字256是已知的，它仍然算作恆定的空間。只需執行線性時間遍歷，就可以得到排序列表。

來源

2017-04-11 07:13:11

「不變的額外空間」意味着您使用相同數量的額外空間，無論輸入字符串的大小如何。

這裏是你如何做到這一點：

創建的256個整數空數組，全部初始化爲0。
對於字符串中的每個字符，字符轉換爲整數，並增加相應的值在數組中。
完成所有字符的處理後，請遍歷數組並輸出出現的字符。

在僞代碼，它看起來是這樣的：

counts = array[256] of int, initialized to 0 
// count character occurrences 
for each char in string 
    index = (int)char 
    counts[index] = counts[index + 1] 

// build string 
outputString = "" 
for index = 0 to 255 
    if (counts[index] > 0) 
     c = (char)index 
     outputString = outputString + repeat(c, counts[index]) 

return outputString;

來源

2017-04-11 15:43:50

如何排序的ASCII字符線性時間和恆定的空間

回答

相關問題