欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

26.Remove Duplicates from Sorted Array

程序员文章站 2022-03-15 20:36:05
...

题目:
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.
解析:移除已排序数组中的重复元素。
方法一:使用指针的方式直接对原数组进行修改。

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

特别注意,如果没有第三条语句,会导致运行超时。一般对这种特殊情况都需要单独处理。
方法二:使用set容器特性-set集合中没有重复的元素,但是不符合题目要求(虽然accetped)有额外的空间资源

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0) return 0;
        set<int> st(nums.begin(),nums.end());
        nums.assign(st.begin(),st.end());
        return nums.size();
    }
};

set是关联式容器,它里面的元素都是排好序的,并且set集合中没有重复的元素。assign将区间[first,last)中的元素赋值到当前的vector容器中。第二种方法的时间复杂度比第一种方法要大。

相关标签: 编程基础