LeetCode 443 压缩字符串

字符数组压缩算法详解：实现与分析

一、引言

在处理字符数组时，我们常常遇到需要对连续重复字符进行压缩的场景。这不仅可以节省存储空间，还能提升数据传输效率。本文将深入解析一个经典的字符数组压缩算法，通过详细的实现步骤和原理分析，帮助读者全面理解这一算法。

二、问题详细描述

给定一个字符数组 chars，请使用以下算法进行压缩：

1. 从一个空字符串 s 开始。

2. 对于 chars 中的每组连续重复字符：

   • 如果这一组长度为 1，则将字符追加到 s 中。

   • 否则，需要向 s 追加字符，后跟这一组的长度。例如，字符 'a' 连续出现 3 次，则压缩为 "a3"。

3. 压缩后得到的字符串 s 不应该直接返回，需要转储到字符数组 chars 中。如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。例如，长度为 12 的组将被写为 '1' 和 '2' 两个字符。

4. 修改完输入数组后，返回该数组的新长度。

三、解题思路：双指针法

3.1 算法原理

为了高效地在原地完成字符数组的压缩，我们采用双指针技术。双指针法通过两个指针 read 和 write 分别负责读取和写入操作，能够在一次遍历中完成压缩，无需额外的空间。

3.2 详细步骤

1. 初始化指针：read 和 write 指针都从 0 开始。

2. 读取字符：read 指针用于遍历字符数组，找到每组连续重复字符。

3. 计数：对于每个字符，计算其连续出现的次数。这通过一个循环实现，每次检查下一个字符是否与当前字符相同，如果是，则计数加 1。

4. 写入字符：将当前字符写入 write 指针位置。然后根据计数决定是否需要写入数字。

5. 写入计数：如果计数大于 1，则将计数转换为字符串，并逐个字符写入 write 指针后续位置。例如，计数为 12 时，写入 '1' 和 '2'。

6. 移动指针：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']

步骤解析：

1. read = 0，current = 'a'，计数为 2。

   • 写入 'a'，write = 1。

   • 写入 '2'，write = 2。

   • read 移动到 2。

2. read = 2，current = 'b'，计数为 2。

   • 写入 'b'，write = 3。

   • 写入 '2'，write = 4。

   • read 移动到 4。

3. read = 4，current = 'c'，计数为 3。

   • 写入 'c'，write = 5。

   • 写入 '3'，write = 6。

   • read 移动到 7，循环结束。

输出：数组变为 ['a', '2', 'b', '2', 'c', '3']，新长度为 6。

示例 2

输入：chars = ['a']

步骤解析：

1. 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']

步骤解析：

1. read = 0，current = 'a'，计数为 1。

   • 写入 'a'，write = 1。

   • read 移动到 1。

2. 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) 空间复杂度下完成任务。该算法的核心在于高效地识别连续重复字符组，并将它们转换为压缩形式。通过详细解析和示例分析，我们希望读者能够深入理解这一算法的原理和实现细节。