删除有序数组中的重复项

2023-10-07 16:02:57 浏览数 (1)

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

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

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

判题标准:

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

代码语言:javascript复制
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

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

assert k == expectedNums.length;
for (int i = 0; i < k; i  ) {
    assert nums[i] == expectedNums[i];
}
代码语言:javascript复制
class Solution {

public:

    int removeDuplicates(vector<int>& nums) {

        int len = nums.size();

        int l = 1, r = 1;//将快慢指针指向下标1,第一个元素无论如何不需要动

        while(l <= r && r < len)//遍历数组

        {

            if(nums[r] != nums[r - 1])//因为数组是有序数组,相等的元素一定是排列在一起的,即下标连续,故可以判断当前元素和上一元素的等价关系

            {

                nums[l  ] = nums[r];//若不等于,即说明快指针找到了下一个不同元素的位置,将其归并到已排列元素(即不同元素的组合)当中,称为不同元素组合当中的最后一位,并将慢指针加1,给下一个不同元素预留位置。

            }

            r  ;//无论如何快指针在每次循环后都往后推一位,因为它只是负责查找的功能。

        }

        return l;//因为l最后代表的是不同元素组合的最后一位元素的下标加1,表明不同元素的最后一位下标为l-1,而数组是从0开始计数的,所以最后不同元素共有(l-1)  1 = l 个。

    }

};

```双指针判断当前元素与上一元素的等价关系。

0 人点赞