[leetcode题解]026.Remove Duplicates from Sorted Array

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]);
}

给定一个已排序的数组,把相邻的重复元素剔除掉只保留一个。比如1,2,2,3,3,3,3,4   操作完之后的结果要求是 1,2,3,4 把连着的两个2多余的去除,只保留一个,连着的4个重复3也同样只保留一个。

思路比较简单,只需要用一个idx来记录上次不重复的最后一个元素,前面遍历元素,遇到不重复的,就在idx后面一个位置更新不重复的元素,然后把idx指向这个新元素的位置即可。

C语言代码如下:

int removeDuplicates(int* nums, int numsSize){
    int i, idx;
    
    if (numsSize == 0) {
        return 0;
    }
    
    idx = 0;
    for (i = 1; i < numsSize; i++) {
        if (nums[i] != nums[idx]) {
            idx++;
            nums[idx] = nums[i];
        }
    }
    
    return idx + 1;
}

C++代码如下:

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

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]026.Remove Duplicates from Sorted Array

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/214.html

相关文章