题目描述
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.
题目思路
代码 C++
- 思路一、从第一位开始，逐一和前一位比较，如果相等就从数组中去除；不等则 i+1，同时从后一位开始比较
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0){
return 0;
}
int length = nums.size();
int aa = nums[0];
int i=1;
while(i < length){
if(nums[i] == aa){
nums.erase(nums.begin() + i);
length--;
}
else{
aa = nums[i];
i++;
}
}
return length;
}
};
- 思路二、看discussion高赞得到的思路，思路很奇妙。
首先，题干最重要条件是，数组有序，该思路充分运用数组有序。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0){
return 0;
}
int length = 1;
for(int i=1; i < nums.size(); i++){
if(nums[i] != nums[i-1]){
nums[length] = nums[i]; // 保证前 length 位是不重复的
length++; // 找到不重复的个数
}
}
return length;
}
};
