算法/數據結構訪談

Question

其目的是就地將a3b5c2這樣的數組轉換爲aaabbbbbcc。 我有一個解決方案：

• 假設陣列是無限的大小，
• 我解析從端部陣列。
• 尋找一個數字（說n）
• 取決於我得到多少位數，我尋找下一個字符。
• 當我得到它時，我將元素從當前位置移動到陣列末端n-1位置。
• 用遇到的字符填充未定位置。

該解決方案的複雜度爲O（n^2）。有複雜度小於O（n^2）的解決方案嗎？

Answer 1

如果您解析數組一次，您可以通過將所有數值相加來知道最後一個元素的位置。

解析一次，找到它的最終大小。

一旦你這樣做，開始從「結束」加油吧（從那裏它的最終值爲）：2次c，然後5倍b ...

這是一個O(n)就地解決方案。

編輯：

由於srbh.kmr在評論中表示，這不會如果數組有一系列嚴重放置文字工作重複一次。例如，如果我們有數組a1b1c1d1e7，上面的答案將刪除最後一個字母。

導致問題的唯一編號爲1，我們可以在O(n)對待它：

治療前陣如上所述，消除這些人。從頭開始，解析數組，每次找到一個1，將其擦除並向前移動剩餘的字母（而不是整個剩餘數組，只是下一個字符）。如果在陣列中發現若干個1，陣列的第一和第二部分之間的孔將變大。對於上面的示例陣列，所述步驟是這樣的：

a1b1c1d1e7 
// First parse gives length = 1+1+1+1+7 

// Repair ones 
a b1c1d1e7 
ab 1c1d1e7 
ab c1d1e7 
abc 1d1e7 
abc d1e7 
abcd 1e7 
abcd e7 
abcde 7 
abcde7 

然後，應用上面的算法。如果在一個字符後沒有找到數字，只需將該字符複製到它在數組末尾的位置：

// Fill final array 
abcde7 x 
     ^11th position 
abcde  e 
abcde ee 
abcde eee 
abcde eeee 
abcde eeeee 
abcdeeeeeee 
abcdeeeeeee // Here we overwrite the first "e" 
abcdeeeeeee // Then we see there are lone letters (4 times), so we leave them.