26.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.
解析:移除已排序数组中的重复元素。
方法一:使用指针的方式直接对原数组进行修改。
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容器中。第二种方法的时间复杂度比第一种方法要大。
推荐阅读
-
【一天一道LeetCode】#26. Remove Duplicates from Sorted Array
-
LeetCode 83. Remove Duplicates from Sorted List
-
83. Remove Duplicates from Sorted List
-
LeetCode 83. Remove Duplicates from Sorted List
-
LeetCode 83. Remove Duplicates from Sorted List ***
-
Leetcode 83. Remove Duplicates from Sorted List
-
Leetcode No.26 Remove Duplicates from Sorted Array(c++实现)
-
26. Remove Duplicates from Sorted Array
-
【LeetCode】80. Remove Duplicates from Sorted Array II (删除排序数组中的重复项 II)-C++实现及详细图解
-
【LeetCode】26. Remove Duplicates from Sorted Array (删除排序数组中的重复项)-C++实现的两种方法