LeetCode26 — Remove Duplicates f

问题描述

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.
Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

解题思路

首先我们要明白，让返回的内容是最后这个数组的长度，因此返回值是nums的大小，之后我们还应该注意到他要求使用O(1)的空间复杂度，那么我们就不能新建一个数组了，那么我们可以再原有数组上进行操作，这也是一个很重要的思想，这样我们既不会破坏我们要遍历的数组，还可以节省空间，那我们就需要一个新的指针去指向这个要生成的数组，具体实现的代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<=1) return nums.size();
        int len=1;
        for(int i=1;i<nums.size();++i)
        {
            if(nums[i]!=nums[i-1])
            {
                nums[len++]=nums[i];
            }
        }
        return len;
    }
};

代码中，我们使用len，让len指向数组的第二个位置，并且从第二个位置开始遍历，当nums[i]不等于nums[i-1]时，我们就让len增加长度，这样我们len最终指向的位置就是我们这个无重复数组的最后一个节点的位置了，这道题为什么说简单呢，因为他将所有的数组都已经重新排列了好了，那么如果我们使用无序序列该怎么办呢，那么添加algorithm.sort()函数即可。