字符數組壓縮算法詳解：實現與分析
一、引言
在處理字符數組時，我們常常遇到需要對連續重復字符進行壓縮的場景。這不僅可以節省存儲空間，還能提升數據傳輸效率。本文將深入解析一個經典的字符數組壓縮算法，通過詳細的實現步驟和原理分析，幫助讀者全面理解這一算法。
二、問題詳細描述
給定一個字符數組 chars，請使用以下算法進行壓縮：
-
從一個空字符串
s開始。 -
對于
chars中的每組連續重復字符：-
如果這一組長度為 1，則將字符追加到
s中。 -
否則，需要向
s追加字符，后跟這一組的長度。例如，字符'a'連續出現 3 次，則壓縮為"a3"。
-
-
壓縮后得到的字符串
s不應該直接返回，需要轉儲到字符數組chars中。如果組長度為 10 或 10 以上，則在chars數組中會被拆分為多個字符。例如，長度為 12 的組將被寫為'1'和'2'兩個字符。 -
修改完輸入數組后，返回該數組的新長度。
三、解題思路：雙指針法
3.1 算法原理
為了高效地在原地完成字符數組的壓縮，我們采用雙指針技術。雙指針法通過兩個指針 read 和 write 分別負責讀取和寫入操作，能夠在一次遍歷中完成壓縮，無需額外的空間。
3.2 詳細步驟
-
初始化指針：
read和write指針都從 0 開始。 -
讀取字符：
read指針用于遍歷字符數組，找到每組連續重復字符。 -
計數：對于每個字符，計算其連續出現的次數。這通過一個循環實現，每次檢查下一個字符是否與當前字符相同，如果是，則計數加 1。
-
寫入字符：將當前字符寫入
write指針位置。然后根據計數決定是否需要寫入數字。 -
寫入計數：如果計數大于 1，則將計數轉換為字符串，并逐個字符寫入
write指針后續位置。例如，計數為 12 時，寫入'1'和'2'。 -
移動指針：
read指針移動到下一組字符的起始位置，write指針根據寫入的字符數量移動。
3.3 優勢
雙指針法的優勢在于：
-
高效性：僅需一次遍歷即可完成壓縮，時間復雜度為 O(n)，其中 n 是數組長度。
-
空間效率：所有操作在原數組上進行，無需額外存儲結構，空間復雜度為 O(1)。
四、算法實現
以下是 Java 實現代碼：
class Solution {public int compress(char[] chars) {if (chars == null || chars.length == 0) return 0;int write = 0;int n = chars.length;for (int read = 0; read < n; ) {char current = chars[read];int count = 1;// 計算連續字符的長度while (read + count < n && chars[read + count] == current) {count++;}// 寫入當前字符chars[write++] = current;// 如果計數大于 1，寫入計數if (count > 1) {String s = String.valueOf(count);for (char c : s.toCharArray()) {chars[write++] = c;}}// 移動讀取指針到下一組字符read += count;}return write;}
}五、代碼詳細解析
5.1 初始化
if (chars == null || chars.length == 0) return 0;
int write = 0;
int n = chars.length;-
首先檢查輸入數組是否為空或長度為 0。如果是，則直接返回 0。
-
初始化
write指針為 0，用于跟蹤寫入位置。 -
獲取數組長度
n，用于后續循環控制。
5.2 外層循環：遍歷字符數組
for (int read = 0; read < n; ) {char current = chars[read];int count = 1;-
read指針從 0 開始，遍歷整個數組。 -
對于每個
read位置的字符，將其存儲在current中，并初始化計數為 1。
5.3 內層循環：計算連續字符長度
while (read + count < n && chars[read + count] == current) {count++;
}-
檢查
read + count是否在數組范圍內，并且下一個字符是否與current相同。 -
如果是，則計數加 1，直到遇到不同的字符或數組末尾。
5.4 寫入字符
chars[write++] = current;-
將當前字符寫入
write指針位置，并將write指針向前移動一位。
5.5 寫入計數
if (count > 1) {String s = String.valueOf(count);for (char c : s.toCharArray()) {chars[write++] = c;}
}-
如果計數大于 1，則將計數轉換為字符串。
-
遍歷字符串的每個字符，并將其逐個寫入數組。例如，計數為 12 時，寫入
'1'和'2'。
5.6 移動讀取指針
read += count;-
將
read指針移動到下一組字符的起始位置，繼續處理下一組字符。
六、算法分析
6.1 時間復雜度
該算法的時間復雜度為 O(n)，其中 n 是字符數組的長度。每個字符僅被處理一次，無論是讀取還是寫入操作。內層循環雖然看似增加了復雜度，但實際上每個字符只被檢查一次，因此總的時間復雜度仍然是線性的。
6.2 空間復雜度
空間復雜度為 O(1)，因為我們沒有使用任何與輸入規模相關的額外存儲結構。所有操作都在原數組上進行，僅使用了幾個變量來輔助操作。
七、示例分析
示例 1
輸入：chars = ['a', 'a', 'b', 'b', 'c', 'c', 'c']
步驟解析：
-
read = 0，current = 'a'，計數為 2。-
寫入
'a'，write = 1。 -
寫入
'2'，write = 2。 -
read移動到 2。
-
-
read = 2，current = 'b'，計數為 2。-
寫入
'b'，write = 3。 -
寫入
'2'，write = 4。 -
read移動到 4。
-
-
read = 4，current = 'c'，計數為 3。-
寫入
'c'，write = 5。 -
寫入
'3'，write = 6。 -
read移動到 7，循環結束。
-
輸出：數組變為 ['a', '2', 'b', '2', 'c', '3']，新長度為 6。
示例 2
輸入：chars = ['a']
步驟解析：
-
read = 0，current = 'a'，計數為 1。-
寫入
'a'，write = 1。 -
因為計數為 1，不寫入數字。
-
read移動到 1，循環結束。
-
輸出：數組仍為 ['a']，新長度為 1。
示例 3
輸入：chars = ['a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b']
步驟解析：
-
read = 0，current = 'a'，計數為 1。-
寫入
'a'，write = 1。 -
read移動到 1。
-
-
read = 1，current = 'b'，計數為 12。-
寫入
'b'，write = 2。 -
寫入
'1'和'2'，write = 4。 -
read移動到 13，循環結束。
-
輸出：數組變為 ['a', 'b', '1', '2']，新長度為 4。
八、常見問題解答
Q1：為什么選擇雙指針法？
雙指針法能夠高效地在原地完成數組的壓縮。它通過兩個指針分別負責讀取和寫入操作，避免了使用額外的存儲空間。這種方法在時間復雜度和空間復雜度上都具有顯著優勢，特別適合處理這類原地修改的問題。
Q2：如何處理計數大于 9 的情況？
當計數大于 9 時，將計數轉換為字符串，然后逐個字符寫入數組。例如，計數為 12 時，寫入 '1' 和 '2'。這種方法確保了所有計數都能正確表示，無論其大小如何。
Q3：算法是否適用于所有長度的數組？
是的。該算法適用于所有長度的數組，包括空數組、單個字符數組以及包含多個重復字符組的數組。在代碼開頭，我們對空數組進行了特殊處理，返回 0。對于其他情況，算法都能正確處理。
九、總結
字符數組壓縮算法是一個典型的原地操作問題，通過雙指針法能夠在 O(n) 時間復雜度和 O(1) 空間復雜度下完成任務。該算法的核心在于高效地識別連續重復字符組，并將它們轉換為壓縮形式。通過詳細解析和示例分析，我們希望讀者能夠深入理解這一算法的原理和實現細節。
)
)
)
)
