題目描述
給你一個有序陣列 nums ，請你 原地 洗掉重復出現的元素，使每個元素 只出現一次 ，回傳洗掉后陣列的新長度，不要使用額外的陣列空間，你必須在 原地 修改輸入陣列 并在使用 O(1) 額外空間的條件下完成，
作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
題目決議
1、首先我們需要明白什么是原地演算法（in-place algorithm），它是一種使用小的，固定數量的額外之空間來轉換資料的演算法，
2、給定的陣列是有序的，不管是升序還是降序，重復出現的元素只可能在相鄰的元素上
題目解答
演算法1，時間復雜度o(n2)直接上代碼，如下：
int process(int * nums,int numsSize)
{
int saveNum=numsSize;
for(int i=numsSize-1;i>0;i--)
{
if(nums[i]==nums[i-1])
{
for(int j=i-1;j<saveNum-1;j++)
{
nums[j]=nums[j+1];
}
saveNum--;
}
}
return saveNum;
}
}
解題思路：有重復元素，我們就洗掉重復元素，陣列中洗掉元素是陣列的基本操作，這個我們都很熟悉，唯一需要注意的是元素洗掉后陣列的長度會變短，因此我們需要注意回圈的結束條件，我們使用兩層回圈，外層回圈遍歷陣列，內層需要執行陣列元素的洗掉操作；由于是洗掉操作，因此外層回圈我們要采用倒敘的方式進行遍歷，內層回圈開始點為要洗掉的元素的索引，結束點為當前陣列所剩余的長度，最后，回傳剩余元素的個數，
演算法2，時間復雜度o(n)，代碼如下：
int process(int* nums, int numsSize){
int l=0;
for(int i=0;i<numsSize;i++)
{
if(l<1||nums[l-1]!=nums[i])
{
nums[l++]=nums[i];
}
}
return l;
}
解題思路：由于陣列是有序的，因此我們用兩個索引來遍歷陣列，第一個索引記錄當前遍歷過的陣列的有限長度，用 l 表示，第二個索引記錄當前遍歷過的陣列，用回圈索引 i 表示，下標為i的元素和下標為l-1的元素，進行比較，不相等則將下標為i的元素賦值給下標為l的元素，此時有限陣列的長度增加了，因此l要進行+1操作；如果相等，則l不動，i繼續往下遍歷，直至遍歷完成，由于i首次遍歷后，陣列的有效長度肯定要加1，當時l-1為非法下標，因此l=0時的遍歷，一定要將陣列的有效長度 l 進行+1操作，for回圈下的l<1的判斷條件就是為了解決這個用例，
兩種演算法已經講完了，歡迎指正批評
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/374377.html
標籤：其他