從排序數(shù)組中刪除重復(fù)項(xiàng)
給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
示例?1:
給定數(shù)組nums=[1,1,2], 函數(shù)應(yīng)該返回新的長度2, 并且原數(shù)組nums 的前兩個元素被修改為1,2。 你不需要考慮數(shù)組中超出新長度后面的元素。
示例?2:
給定 nums =[0,0,1,1,1,2,2,3,3,4],函數(shù)應(yīng)該返回新的長度5, 并且原數(shù)組nums 的前五個元素被修改為0,1,2,3,4。你不需要考慮數(shù)組中超出新長度后面的元素。
說明:
為什么返回數(shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
請注意，輸入數(shù)組是以“引用”方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
你可以想象內(nèi)部操作如下:
//nums是以“引用”方式傳遞的。也就是說，不對實(shí)參做任何拷貝int len = removeDuplicates(nums);// 在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中該長度范圍內(nèi)的所有元素。for (int i = 0; i < len; i++) {? ? print(nums[i]);}
這道題的難點(diǎn)只是在于空間復(fù)雜度的要求為O(1)?
有利的條件是它是一個排序過了的數(shù)組
為了達(dá)到這個要求,一種好的解決方法是使用雙指針 即只使用一個額外的int來記錄數(shù)組的索引 同時也可以達(dá)到一些其他的目的.
對于本題 既然要刪除重復(fù)項(xiàng) 那么遍歷一遍數(shù)組是肯定不能少的? 而使用一個額外的指針 就可以達(dá)到在遍歷的同時,完成對刪除重復(fù)項(xiàng)要求的滿足? 枯講無味 直接上代碼看吧
public class Solution {
? ? public int RemoveDuplicates(int[] nums) {
? ? ? ? if (nums.Length==0)
? ? ? ? ? ? return 0;
? ? ? ? int numbers=0;
? ? ? ? for( int i = 0 ;i < nums.Length; i++){
? ? ? ? ? ? if (nums[i]!=nums[numbers]) {numbers++;nums[numbers]=nums[i];}
? ? ? ? }
? ? ? ? return numbers+=1;
? ? }
}
重點(diǎn)在于理解 為什么?if (nums[i]!=nums[numbers])? 要進(jìn)行 numbers++和nums[numbers]=nums[i];
你可以理解為 numbers這個額外指針 記錄了非重復(fù)數(shù)字的"個數(shù)" 剛開始是0個 遇到了不同的數(shù)字 把第numbers(剛開始是0)個位置的數(shù)字替換成這個不重復(fù)的數(shù)字 并且計數(shù)(++) 這樣就達(dá)到了去掉重復(fù)數(shù)字的目的 并且還記錄了重復(fù)數(shù)字的個數(shù) 至于為什么是return numbers+1 多讀一讀 想一想最開始時候的情況 你也就明白了. 因?yàn)閯傞_始時候都是0 而兩個指針指向相同, 第0個數(shù)字就沒有算進(jìn)去而已.
