開源地址：https://github.com/jiauzhang/algorithms
題目描述
/*
* https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
* 給定一個排序陣列，你需要在原地洗掉重復出現的元素，使得每個元素只出現一次，
* 回傳移除后陣列的新長度，
* 不要使用額外的陣列空間，你必須在原地修改輸入陣列
* 并在使用 O(1) 額外空間的條件下完成，
*/
示例
/*
* 示例 1:
* 給定陣列 nums = [1,1,2],
* 函式應該回傳新的長度 2, 并且原陣列 nums 的前兩個元素被修改為 1, 2，
* 你不需要考慮陣列中超出新長度后面的元素，
*
* 示例 2:
* 給定 nums = [0,0,1,1,1,2,2,3,3,4],
* 函式應該回傳新的長度 5, 并且原陣列 nums 的前五個元素被修改為 0, 1, 2, 3, 4，
*
* 注：
* 你不需要考慮陣列中超出新長度后面的元素，
*/
解題思路
/*
* 1. 題目的意思其實就是將不同的數字向前緊密排列，因此涉及到下一個新的數字
* 放在哪里，即需要一個索引值指定，還需要知道最新的數字在哪里，即又需要
* 一個索引值
* 2. 因此使用兩個索引值，相同時一個前移、一個不動；
* 遇到不同時，前邊的指標前移并將新的數字復制過來，然后走的快的
* 指標繼續前移，如此反復即可
*/
示例代碼
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() <= 1)
return nums.size();
int head = 0, tail = 0;
while (tail < nums.size()) {
if (nums[head] == nums[tail]) {
tail++;
} else {
head++;
if (head < tail) {
nums[head] = nums[tail];
tail++;
}
}
}
nums.resize(head+1);
return head+1;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10533.html
標籤：其他