C++高手教你秒删数组重复元素

C++高手教你秒删数组重复元素

在C++编程中，删除数组中的重复元素是一项常见的任务。双指针法是一种高效且简洁的解决方案，它可以在O(n)时间内完成这一操作。本文将深入讲解双指针法的原理和实现细节，并通过具体代码示例帮助你掌握这一技巧。

双指针法的核心思想是使用两个指针（通常称为快指针和慢指针）来遍历数组。快指针负责扫描整个数组，而慢指针则用于记录不重复元素的位置。当快指针遇到一个与慢指针所指元素不同的新元素时，就将该元素移动到慢指针的下一个位置，并将慢指针向前移动一位。这样，慢指针之前的数组部分就始终保持着不重复的元素序列。

让我们通过一个具体的例子来理解双指针法的实现过程。假设我们有一个数组nums，其中包含一些重复的元素，我们的目标是删除这些重复元素，并返回处理后的数组长度。

#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }
    
    int slow = 0; // 慢指针，初始位置为0
    for (int fast = 1; fast < nums.size(); ++fast) {
        // 如果快指针指向的元素与慢指针指向的元素不同
        if (nums[fast] != nums[slow]) {
            // 将慢指针向前移动一位
            ++slow;
            // 将快指针指向的元素复制到慢指针的位置
            nums[slow] = nums[fast];
        }
    }
    
    // 慢指针的下一个位置就是新数组的长度
    return slow + 1;
}

int main() {
    std::vector<int> nums = {1, 1, 2, 2, 3, 4, 4, 5};
    int newLength = removeDuplicates(nums);
    
    std::cout << "New length: " << newLength << std::endl;
    std::cout << "Modified array: ";
    for (int i = 0; i < newLength; ++i) {
        std::cout << nums[i] << " ";
    }
    
    return 0;
}

这段代码中：

1. slow是慢指针，初始位置为0
2. fast是快指针，从1开始遍历数组
3. 当nums[fast]与nums[slow]不同时，将nums[fast]复制到nums[slow+1]的位置，并将slow向前移动一位
4. 最后，slow+1就是新数组的长度

双指针法的时间复杂度为O(n)，其中n是数组的长度。这是因为每个元素最多被访问两次：一次由快指针，一次由慢指针。空间复杂度为O(1)，因为我们只使用了常数个额外变量。

双指针法在面试和实际开发中都非常常见。例如，在LeetCode的第26题"删除排序数组中的重复项"中，就要求使用双指针法在O(n)时间内删除重复元素。此外，在处理大量数据时，双指针法的高效性使其成为处理数组和链表问题的首选方法。

双指针法是一种简单而强大的算法，特别适合处理数组和链表中的元素删除问题。通过使用快慢两个指针，我们可以在一次遍历中完成元素的去重，既节省了时间，又避免了额外的空间开销。掌握双指针法，不仅能帮助你轻松应对相关面试题，还能让你在实际开发中写出更高效、更优雅的代码。