删除有序数组中的重复项

删除有序数组中的重复项

题目描述

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回k 。

判题标准:

系统会用下面的代码来测试你的题解:

1
2
3
4
5
6
7
8
9
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被通过。

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列

代码实现

法1：重构 (非原地)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()||nums.size()==1){
            return nums.size();
        }
        vector<int> nums2;
        for(vector<int>::iterator it=nums.begin();it!=nums.end()-1;it++){
            if(*it!=*(it+1)){
                nums2.push_back(*it);
            }
        }
        nums2.push_back(nums.back());
        nums.swap(nums2);
        return nums.size();
    }
};
int main(){
    vector<int>nums = {1,1,2};
    Solution s;
    int i=s.removeDuplicates(nums);
    cout<<i<<endl;
    return 0;
}

法2：使用双指针技术（原地）

一个指针用于遍历数组，另一个指针用于指向下一个不重复元素应该插入的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int removeDuplicates(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        int i = 0; // 慢指针，指向下一个不重复元素应该存放的位置
        for (int j = 1; j < nums.size(); j++) { // 快指针，用于遍历整个数组
            if (nums[j] != nums[i]) {
                i++; // 当找到不重复的元素时，移动慢指针
                nums[i] = nums[j]; // 将不重复的元素复制到慢指针的位置
            }
            // 不需要显式删除元素，因为慢指针会自动覆盖重复的元素
        }
        return i + 1; // 返回新数组的长度（即不包含重复元素的长度）
    }
};
int main(){
    vector<int>nums = {1,1,2};
    Solution s;
    int i=s.removeDuplicates(nums);
    cout<<i<<endl;
    return 0;
}

双指针方法是一种在处理数组或类似数据结构时常用的技巧，它通过同时使用两个指针（或索引）来遍历数据，以达到优化算法性能的目的。在您提供的修正后版本的代码中，双指针方法被用于删除已排序数组中的重复项。下面我将详细解释这个双指针方法的工作原理和步骤。

双指针方法的工作原理

  1. 初始化指针：
    • 在这个例子中，我们定义了两个指针（或索引）i 和 j。i 是慢指针，初始化为0，表示下一个不重复元素应该存放的位置。j 是快指针，初始化为1，用于遍历整个数组（从第二个元素开始）。
  2. 遍历数组：
    • 快指针j 遍历整个数组，而慢指针 i 只在找到不重复元素时才移动。这种机制确保了只有不重复的元素才会被保留在数组的前部分。
  3. 比较与移动：

    • 在每次迭代中，我们比较

      1
      nums[j]

      （快指针指向的元素）和

      1
      nums[i]

      （慢指针指向的元素）。

      • 如果nums[j] 不等于 nums[i]，说明我们找到了一个新的不重复元素。此时，我们将 nums[j] 复制到 nums[i+1] 的位置（注意是 i+1，因为 i 指向的是当前不重复序列的最后一个元素的索引），然后递增 i，以便为下一个不重复元素腾出空间。
      • 如果nums[j] 等于 nums[i]，则不做任何操作，因为我们已经有一个相同的元素在 nums[i] 的位置了，继续向前移动快指针 j。
  4. 确定新数组长度：
    • 遍历结束后，i 的值将是不重复元素序列的最后一个元素的索引。由于数组索引是从0开始的，所以新数组（即不包含重复元素的数组）的长度是 i + 1。

优点

  • 时间复杂度低：双指针方法通常可以将时间复杂度降低到O(n)，其中n是数组的长度。这是因为每个元素最多被访问两次（一次由快指针，一次可能被复制到慢指针的位置）。
  • 空间复杂度低：该方法在原地修改数组，不需要额外的存储空间（除了几个用于迭代的变量），因此空间复杂度为O(1)。

应用场景

双指针方法特别适用于处理已排序或具有某种单调性的数组或链表，如删除重复项、查找特定条件的两个元素、归并排序中的合并过程等。

总之，双指针方法是一种高效且实用的算法技巧，在处理数组和链表等数据结构时能够显著优化算法的性能。