深入解析有序数组去重：从双指针思维到高效实战

2026-02-03 18:50:48 0条评论 3次阅读 0人点赞

引言

在数据清洗和算法面试中，处理重复数据是一项非常基础但又至关重要的技能。想象一下，当你从数据库导出了一份按时间排序的日志，或者是传感器传回的一连串递增的温度读数，中间往往夹杂着大量的重复记录。如何既快速又节省空间地清理这些数据？这就是我们今天要解决的核心问题。

通常，新手开发者可能会想到使用哈希表或者创建一个新的数组来存储去重后的结果。虽然这在逻辑上是可行的，但在处理海量数据或内存受限的环境（如嵌入式系统）中，额外的内存开销往往是不可接受的。面试官也通常会提出更严格的要求：“请在原地进行修改，不要使用额外的数组空间。”

在这篇文章中，我们将深入探讨这道经典的算法题——从有序数组中删除重复项。我们将从最直观的思路出发，逐步推导出最优的双指针解法，详细剖析其背后的逻辑，并通过完整的代码示例和常见陷阱分析，帮助你彻底掌握这一技巧。无论你是为了准备面试，还是为了优化实际项目中的代码，我相信你都会有所收获。

问题描述与约束

首先，让我们明确问题的具体定义和约束条件。这不仅仅是关于写代码，更是关于理解“边界”和“规则”。

问题陈述：

给定一个按非递减顺序排序的整数数组 nums，你的任务是原地移除数组中重复出现的元素，使得每个元素只出现一次。最后，你需要返回移除重复项后数组的新长度。

这里有几个关键点需要特别注意：

  • 原地修改：这意味着我们不能申请新的数组来存放结果。我们必须直接在输入的 nums 数组上进行操作，覆盖掉不需要的元素。
  • $O(1)$ 额外空间：除了几个变量外，我们使用的内存不应随数组大小 $N$ 的增加而增加。
  • 返回值是长度：虽然我们修改了数组，但函数只需要返回新数组的长度。通常，判题系统会检查 nums 的前 $k$ 个元素（其中 $k$ 是返回的长度）是否正确且不重复，而 $k$ 之后的元素是什么则不予关心。

示例分析

为了让我们对问题有更直观的理解，让我们看两个具体的例子。

#### 示例 1：简单情况

输入：nums = [1, 1, 2]
处理过程：

  • 我们有两个 1，只需要保留一个。
  • 我们把后面的 2 向前移动。

输出：INLINECODEaab433e0, 且 INLINECODE0c212945 的前两个元素变为 [1, 2]。
(注：数组第三个位置可以是任意值，比如 _ 表示我们不关心的旧数据)

#### 示例 2：复杂情况

输入：nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

在这个例子中，数字 INLINECODE0293e5ef 和 INLINECODE4fa16989 都出现了三次，我们需要把多余的全部“挤”出去。

输出：INLINECODEd995d5e4, 且 INLINECODE5a516195 的前五个元素变为 [0, 1, 2, 3, 4]。

解决方案：双指针法（快慢指针）

为什么选择双指针？

既然数组是有序的，这给了一个极其重要的提示：重复的元素一定是相邻的。

如果数组是无序的，比如 INLINECODE159a91a8，我们需要记录出现过哪些数字，可能需要哈希表。但在有序数组 INLINECODE69e71f34 中，我们只需要关心“当前元素”和“前一个元素”的关系。这种局部性特点，使得我们可以通过线性扫描一次性解决问题，而双指针正是处理这类线性数组修改的利器。

算法核心思路

我们可以定义两个指针，形象地称为“慢指针”和“快指针”：

  • 慢指针：我们可以将其命名为 INLINECODE8a4a9cfd（在上文的代码中用 INLINECODEb1e54864 表示）。它始终指向当前已经处理好的、不含重复元素的序列的最后一个位置。你可以把它看作是“构建中新数组的队尾”。
  • 快指针：我们可以将其命名为 INLINECODE75671f76（在上文的代码中用 INLINECODE91cd9420 表示）。它的任务是像扫描仪一样，快速地向后遍历，寻找那些“新面孔”（不重复的元素）。

工作流程：

  • 快指针在前面“探路”，每发现一个不重复的元素，就把它“拷贝”给慢指针的下一个位置。
  • 慢指针每接收一个新元素，就向前移动一步，扩充有效区域。
  • 这样，当我们遍历结束时，慢指针所在的位置（或其索引 + 1）就是新数组的长度。

详细步骤解析

让我们把算法分解成细致的步骤，确保没有任何模糊之处。

1. 边界检查（防御性编程）

首先，我们必须考虑数组为空的情况。如果 INLINECODE784b90e6 为空，访问 INLINECODEc790f59a 会导致越界错误。因此，第一步总是检查大小。

2. 初始化

  • 数组的第一个元素 nums[0] 肯定是保留的，因为它前面没有元素可以比较。
  • 因此，慢指针 INLINECODEb324b127 初始化为 INLINECODEde5f0c67。这代表两个含义：下一个唯一元素应该放的位置，以及当前唯一元素的数量。
  • 快指针 INLINECODE3cc8cd18 从 INLINECODE7787a937 开始遍历，直到数组末尾。

3. 比较与决策

在循环中，我们比较 INLINECODEef696be3（当前扫描到的元素）与 INLINECODE264118bb（前一个元素）。

  • 情况 A：发现重复 (nums[j] == nums[j-1])

这意味着 INLINECODE893ce1ad 是一个“旧值”。我们不需要它。此时，我们只移动快指针 INLINECODE2a0bbda8，继续向后寻找。慢指针 i 保持不动。

  • 情况 B：发现新值 (nums[j] != nums[j-1])

这是一个关键时刻！这意味着 nums[j] 是一个新的、唯一的元素。我们需要把它加入到我们的结果集中。

– 执行赋值：INLINECODEf5d359a7。我们将新值覆盖到 INLINECODEbe1ae68d 的位置。

– 移动慢指针：i++。现在的有效区域变长了。

– 移动快指针：j++（通常由循环自动完成）。

4. 结束

当 INLINECODE2eb87af2 走完数组后，INLINECODE1548dbf1 的值恰好就是唯一元素的个数（因为 i 是从 1 开始计数的，且每次遇到新值才加 1）。

完整代码实现 (C++)

让我们把上面的逻辑转化为严谨的 C++ 代码。注意其中的注释细节。

#include 
using namespace std;

class Solution {
public:
    int removeDuplicates(vector& nums) {
        // 步骤 1: 处理特殊情况
        // 如果数组为空，没有元素需要处理，直接返回 0
        if (nums.size() == 0) {
            return 0;
        }
        
        // 步骤 2: 初始化指针
        // i 是慢指针，表示下一个不重复元素应该放置的索引
        // 也是当前有效数组的长度计数器
        int i = 1; 
        
        // 步骤 3: 遍历数组
        // j 是快指针，用于扫描整个数组
        // 注意我们从 1 开始，因为第 0 个元素默认保留
        for (int j = 1; j < nums.size(); j++) {
            
            // 步骤 4: 核心判断
            // 因为数组是有序的，我们只需要比较当前元素和前一个元素
            if (nums[j] != nums[j-1]) {
                // 如果不相等，说明遇到了一个新的唯一元素
                // 将这个新元素复制到慢指针 i 的位置
                nums[i] = nums[j];
                
                // 慢指针向前移动，准备接收下一个唯一元素
                i++;
            }
            // 如果相等，什么都不做，快指针 j 继续向前移动（循环自增）
        }
        
        // 步骤 5: 返回结果
        // i 的值现在等于去重后数组的长度
        return i;
    }
};

代码示例 (Python)

为了照顾不同语言习惯的开发者，这里提供同样逻辑的 Python 实现。Python 的代码更加简洁，但逻辑是完全一致的。

def removeDuplicates(nums):
    # 特殊情况：空列表
    if not nums:
        return 0
    
    # 初始化插入位置（慢指针）
    insert_pos = 1
    
    # 从第二个元素开始遍历（快指针）
    for i in range(1, len(nums)):
        # 如果发现当前元素与前一个不同
        if nums[i] != nums[i-1]:
            # 将新元素放到插入位置
            nums[insert_pos] = nums[i]
            # 插入位置后移
            insert_pos += 1
            
    return insert_pos

代码示例 (Java)

Java 开发者在面试中经常使用这种写法，注意数组长度的获取方式。

class Solution {
    public int removeDuplicates(int[] nums) {
        // 边界检查
        if (nums.length == 0) return 0;
        
        // 慢指针 i
        int i = 1;
        
        // 快指针 j 遍历数组
        for (int j = 1; j < nums.length; j++) {
            // 发现新元素
            if (nums[j] != nums[j-1]) {
                nums[i] = nums[j];
                i++;
            }
        }
        
        return i;
    }
}

复杂度深度分析

在算法面试中，只写出代码是不够的，你还需要能够清晰地分析算法的效率。

时间复杂度：$O(N)$

这里的 $N$ 是数组的长度。

  • 我们只使用了一个 for 循环。
  • 在循环内部，所有的操作（赋值、比较、指针移动）都是常数时间操作 $O(1)$。
  • 为什么这是最优的？ 因为我们必须至少检查每一个元素一次才能确定它是否重复。所以，$O(N)$ 是这个问题的理论下限，不可能有比线性时间更快的算法。

空间复杂度：$O(1)$

  • 我们没有分配任何新的数组结构（如 INLINECODEf43eeea9 或 INLINECODE1cb25a83）。
  • 我们只使用了 INLINECODEf0f5fb35 和 INLINECODE75f4dfea 两个整型变量。
  • 无论输入数组有 10 个元素还是 1000 万个元素，我们使用的额外内存空间都是固定的。这完美满足了题目中“原地修改”的要求。

常见陷阱与调试技巧

在实际编码和面试中，很多开发者（包括经验丰富的老手）容易在以下这些细节上犯错。让我们逐一击破。

1. 指针初始化的陷阱

错误做法：将 INLINECODE33f3ce92 初始化为 INLINECODE683106ec，或者将 INLINECODE1d6fa661 初始化为 INLINECODE63d359f6。
后果：这会导致逻辑混乱。如果从 INLINECODEc11e81f8 开始，你需要处理 INLINECODE0ffd6037 这种非法访问，或者在循环内部写复杂的 if-else 来处理第一个元素的特殊情况。
最佳实践：利用“第一个元素默认保留”的特性，直接从 1 开始。这是最简洁的逻辑。

2. 比较对象的错位

错误做法：if (nums[j] != nums[i])。
分析：这是一个非常微妙的逻辑错误。

  • 如果数组是 [1, 2, 2, 3]。
  • 当 INLINECODEcae413b2, INLINECODE84d22174 时，INLINECODE5d03b901 (值为2) 和 INLINECODEbb8f5619 (值为2) 相等，不操作。这没问题。
  • 但如果数组是 INLINECODEc69e098e，当 INLINECODE37ed8a2f, INLINECODE4c74151f 时，两者相等，INLINECODE30b35633 没动。当 INLINECODE0d935f84 时，INLINECODE823bfa48 (值为2) 和 INLINECODE3f3cc6e9 (值为1) 不相等。此时 INLINECODE3102a3a4 被赋值给 INLINECODE7cf71c82，数组变成 INLINECODEf53bf2e8。逻辑似乎暂时成立，但变量语义发生了混乱。i 丢失了“前一个有效元素”的含义。

最佳实践：始终比较 INLINECODE6e1b6a56 (当前扫描项) 和 INLINECODE271b1bf4 (扫描项的前驱)。这样逻辑最稳健：只要跟前一个不一样，就是新元素。

3. 理解“返回值”的误区

很多新手会困惑：“如果我不删除后面的元素，只改了前面的，返回值有什么用？”

解释：在 C++ 或 Java 中，数组是固定长度的容器，你无法真正物理上“删除”数组末尾的空间。所谓的“删除”，在计算机科学中，通常只是逻辑上的隔离。通过返回一个新的长度 INLINECODE684126f5，我们在逻辑上告诉调用者：“这个数组只有前 INLINECODEdaf8c718 个元素是有效的，后面的你可以忽略。”

4. 忽略空数组检查

代码：int i = 1; for (int j = 1; ...)

如果 INLINECODEf28c2c74 为空，INLINECODEe7ee9fbd 是未定义行为。虽然在 Python 中 INLINECODEfd42dea0 不会报错，但在强类型语言中直接访问 INLINECODE0b5e72f3 会导致程序崩溃。这通常是面试官会注意到的第一个细节。

实际应用场景与扩展

理解这个算法不仅仅是为了做题，它在实际开发中也有很多应用场景。

1. 日志数据清洗

当你在处理服务器日志时，日志往往是按时间戳排序的。如果系统在某些状态下报错，可能会产生连续相同的错误日志。在进行大数据分析（如使用 MapReduce 或 Spark）之前，使用这种算法在内存中进行预去重，可以显著减少网络传输和磁盘 I/O 的开销。

2. 传感器数据平滑

在物联网中，传感器可能会在短时间内发送大量相同的读数（例如温度在 0.1 秒内没有变化）。为了节省带宽，我们可以在发送数据包之前，先在设备端运行一次去重算法，只发送变化了的数据点。

3. 进阶思考：允许最多两次重复

LeetCode 上有一道进阶题：“Remove Duplicates from Sorted Array II”，要求每个元素最多出现两次。你会怎么修改这道题的代码？

思路提示：

我们依然可以使用双指针。区别在于判断条件。

  • 我们不再比较 INLINECODEb89cfd99 和 INLINECODE7f8e0df5。
  • 我们需要比较 INLINECODE15bee8db 和 INLINECODEb798ffc2（即当前要填充位置的前两个元素）。
  • 如果 nums[j] > nums[i-2]（假设升序），说明当前元素还没出现过两次，可以填入。

这个问题是对双指针思想的一个绝佳延伸，建议你动手试一试！

总结

今天，我们不仅解决了一道算法题，更重要的是掌握了一种处理数组的思维方式——双指针法。通过将“遍历”和“处理”分离，我们实现了在 $O(N)$ 时间复杂度和 $O(1)$ 空间复杂度下的完美操作。

回顾一下我们的核心要点：

  • 利用有序性：重复元素相邻是使用双指针的前提。
  • 明确指针职责：快指针负责找不同，慢指针负责占坑位。
  • 注意边界细节：空数组检查和正确的初始化是代码健壮性的保证。
  • 原地修改的含义：理解逻辑删除而非物理删除是理解数组操作的关键。

希望这篇深度解析能帮助你从原理到实践彻底掌握这个知识点。下次当你面对需要原地修改数组的问题时，不妨先问问自己：“我能不能用双指针来解决它？”

祝你编码愉快，在技术的道路上不断前行！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/22724.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年