題目：
給定一個排序數(shù)組，你需要在原地刪除重復出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度逛钻。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成锰提。
示例 1:
給定數(shù)組 *nums* = **[1,1,2]**,
函數(shù)應該返回新的長度 **2**, 并且原數(shù)組 *nums* 的前兩個元素被修改為 **`1`**, **`2`**曙痘。
你不需要考慮數(shù)組中超出新長度后面的元素。
示例 2:
給定 *nums* = **[0,0,1,1,1,2,2,3,3,4]**,
函數(shù)應該返回新的長度 **5**, 并且原數(shù)組 *nums* 的前五個元素被修改為 **`0`**, **`1`**, **`2`**, **`3`**, **`4`**立肘。
你不需要考慮數(shù)組中超出新長度后面的元素边坤。
說明:
為什么返回數(shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
請注意赛不，輸入數(shù)組是以“引用”方式傳遞的惩嘉，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
你可以想象內(nèi)部操作如下:
// **nums** 是以“引用”方式傳遞的踢故。也就是說文黎，不對實參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中**該長度范圍內(nèi)**的所有元素殿较。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
分析：
- 1耸峭，額外題設
排序數(shù)組，額外空間復雜度為 O(1)淋纲。 - 2劳闹，算法分析
本題中只要求了額外空間復雜度，而沒對時間復雜度進行限制洽瞬。所以本涕，常規(guī)方法是遍歷數(shù)組，對比相鄰兩個數(shù)值伙窃，將不重復元素保留菩颖，重復元素被覆蓋，最后刪除末尾剩余的元素即可为障。
//常規(guī)方法
class Solution {
public:
/**
* @param A: a list of integers
* @return : return an integer
*/
int removeDuplicates(vector<int> &nums) {
if (nums.empty()) {
return 0;
}
int n = nums.size(), k = 0;
if (n == 1) {
return 1;
}
for (int i = 0; i < n; i++) {
if (nums[i] != nums[k]) {
nums[++k] = nums[i];
}
}
nums.resize(k+1);
return k+1;
}
};
上面代碼在LeetCode上的運行時間為24 ms晦闰。
