力扣80——刪除排序數組中的重複項 II
- 2019 年 12 月 31 日
- 筆記
原題
給定一個排序數組，你需要在原地刪除重複出現的元素，使得每個元素最多出現兩次，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組並在使用 O(1) 額外空間的條件下完成。
示例 1:
給定 nums = [1,1,1,2,2,3], 函數應返回新長度 length = 5, 並且原數組的前五個元素被修改為 1, 1, 2, 2, 3 。 你不需要考慮數組中超出新長度後面的元素。
示例 2:
給定 nums = [0,0,1,1,1,1,2,3,3], 函數應返回新長度 length = 7, 並且原數組的前五個元素被修改為 0, 0, 1, 1, 2, 3, 3 。 你不需要考慮數組中超出新長度後面的元素。
說明:
為什麼返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對於調用者是可見的。
你可以想像內部操作如下:
// nums 是以「引用」方式傳遞的。也就是說，不對實參做任何拷貝 int len = removeDuplicates(nums); // 在函數里修改輸入數組對於調用者是可見的。 // 根據你的函數返回的長度, 它會列印出數組中該長度範圍內的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
原題url：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
解題
本題比較噁心的地方在於針對重複的數字，可以最多留2個，而並不是全部刪除，因此在這點上需要注意。可以用一個專門的變數記錄當前數字重複的次數，當重複次數大於2的時候則直接刪除該數字，當不同後，再將該變數重置。
讓我們看一下程式碼：
class Solution { public int removeDuplicates(int[] nums) { if (nums.length <= 1) { return nums.length; } int start = 1, current = 1; // 已經出現過的數字before，及其出現的次數 int before = nums[0]; int times = 1; while (current < nums.length) { // 相同並且超過2個，則直接跳過 if (nums[current] == before && times == 2) { current++; continue; } // 相同但是不超過2個 // 如果和之前一個數相同，則增加times if (nums[current] == before) { times++; } // 如果不相同，則重置times else { times = 1; } // 賦值，即拷貝該數到合適的位置 nums[start] = nums[current]; before = nums[current]; // 移動指針 current++; start++; } return start; } }
提交OK，執行用時：1 ms，記憶體消耗：37.3 MB。應該沒什麼問題了。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。
這已經是第9篇刷題的文章了，都是 medium 難度，感覺 medium 難度的話，重點關注的是一些邊界判斷，思考是否嚴謹，至於演算法，還是比較基礎的。不知道大家感覺如何。
有興趣的話可以訪問我的部落格或者關注我的公眾號，說不定會有意外的驚喜。
https://death00.github.io/
