Remove Duplicates from Sorted Array

    xiaoxiao2022-07-13  148

    1,题目要求

    Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

    Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

    Example 1: Given nums = [1,1,2],

    Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

    It doesn’t matter what you leave beyond the returned length.

    Example 2: Given nums = [0,0,1,1,1,2,2,3,3,4],

    Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

    It doesn’t matter what values are set beyond the returned length.

    给定排序的数组nums,就地删除重复项,使每个元素只出现一次并返回新的长度。

    不要为另一个数组分配额外的空间,必须通过使用O(1)额外内存修改输入数组来实现此目的。

    2,题目思路

    对于这道题,要求将一个经过排序的数组内的所有重复的数字删除,并返回最后数组的长度。

    如果没有空间为O(1)的要求,那么我们可以很简单的使用set,将数组中的每个元素加入到set中,然后直接返回size即可。 但是这样做是不满足题意的,因为题目函数传入的参数是nums的一个引用,要求不开辟新的空间,而且需要在原nums上进行一个修改,让该nums就是真实的结果。

    因为给定的数组是已经过排序的数组,因此,只要是重复的数字,就一定是挨在一起的。

    在解决这个问题上,我们可以定义一个参数dupCount,用来表示重复的数字的个数。 例如,对于[1, 1, 2],dupCount = 1 这样,我们在进行遍历时,记录当前数字之前的重复数字的个数,只要找到与前一个数字不同的数字——即非重复的数字,就“跨越dupCount个数字”,让它和彼此不重复的数字紧挨着。

    这样一趟遍历下来,我们就有了n - dupCount个不重复的数字,连续存储在数组的前方。其中n为数组的长度。 因此,接下来,我们只需要调用vector的erase函数,将之后所有的元素删除即可。

    3,代码实现

    int x = []() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); return 0; }(); class Solution { public: int removeDuplicates(vector<int>& nums) { int n = nums.size(); if(n <= 1) return n; int dupCount = 0; for(int i = 1;i<n;i++){ if(nums[i] == nums[i-1]) dupCount++; else nums[i-dupCount] = nums[i]; } nums.erase(nums.begin()+n-dupCount, nums.end()); return nums.size(); } };
    最新回复(0)