題目描述
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.
給定一個排序數(shù)組，你需要在 原地 刪除重復(fù)出現(xiàn)的元素丽啡，使得每個元素只出現(xiàn)一次谋右，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間补箍，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成改执。
題解
給定的是有序數(shù)組，如果數(shù)組中存在重復(fù)元素坑雅，那么一定是連續(xù)出現(xiàn)的辈挂。所以，我們這里使用兩個指針：一個指向第一個元素idx裹粤，表明不重復(fù)子數(shù)組的右邊界终蒂；另一個從第二個元素開始進(jìn)行遍歷，i遥诉。
- 依次比較nums[i]和nums[idx]的關(guān)系拇泣，
- 如果不相等，將nums[i]納入到不重復(fù)有序子數(shù)組中矮锈；
- 如果相等霉翔，繼續(xù)下一次循環(huán)，即增加i苞笨。
- 最后债朵，循環(huán)結(jié)束，idx指向的是不重復(fù)有序子數(shù)組的右邊界猫缭，idx+1表示其數(shù)組長度葱弟，返回idx+1即可。
完整代碼：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int idx = 0;
for (int i=1; i< nums.size(); i++){
if (nums[i] != nums[idx])
nums[++idx] = nums[i];
}
return idx+1;
}
};
歡迎關(guān)注公眾號猜丹，一起學(xué)習(xí)
