題目描述：
給你一個有序陣列 nums ，請你 原地 洗掉重復出現的元素，使每個元素 只出現一次 ，回傳洗掉后陣列的新長度，
不要使用額外的陣列空間，你必須在 原地 修改輸入陣列 并在使用 O(1) 額外空間的條件下完成，
輸入：nums = [1,1,2]
輸出：2, nums = [1,2]
解釋：函式應該回傳新的長度 2 ，并且原陣列 nums 的前兩個元素被修改為 1, 2 ，不需要考慮陣列中超出新長度后面的元素，
分析：
我們很容易想到的方法就是暴力求解法：
指定一個i和j變數，i指示當前的位置，j用于向后檢測，如果遇到相同數字，則將資料全部往前挪
圖解：
但這是最基本的暴力求解法，復雜度已經高達o(n2),所以這種方法顯然不行
我們可以考慮使用雙指標法,可將復雜度提升至o(n)
用一個slow指標來依次存盤元素，用fast來檢測是否有相等元素
當slow與fast相等時，直接fast++
slow與fast不等,先slow++，將fast賦給slow,之后fast++
最后回傳元素個數，我們回傳slow+1即可
圖解：
代碼實作
int removeDuplicates(int* nums, int numsSize){
if(!numsSize)
{
return 0;
}
int slow=0;
int fast=0;
while(fast<numsSize)
{
if(nums[fast]==nums[slow])
{
fast++;
}
else
{
slow++;
nums[slow]=nums[fast];
fast++;
}
}
return slow+1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/317926.html
標籤：其他
上一篇：電子專業學生的學習路線
下一篇：初階資料結構——線性表——順序表