刪除排序數組中的重復項 II題目

給定一個增序排列數組 nums ，你需要在 原地 刪除重復出現的元素，使得每個元素最多出現兩次，返回移除后數組的新長度。

不要使用額外的數組空間，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。(來源LeetCode 80)

例子

示例1

輸入：nums = [1,1,1,2,2,3]

輸出：5, nums = [1,1,2,2,3]

示例2

輸入：nums = [0,0,1,1,1,1,2,3,3]
輸出：7, nums = [0,0,1,1,2,3,3]

示例3

輸入：nums =?[1,1,1,1]

輸出：2, nums = [1,1]解題思路

這道題目其實是前面我們有聊過的“刪除排序數組中的重復項“的進階版，其實我們直接的思路大體相似，無非這道題目是使每個元素最多出現兩次，當然代碼實現上會稍微復雜一些，注意的條件也比較多。

思路一：我們還是遍歷數組，我們可以從第三個元素開始遍歷，當nums[i]==nums[i-2]時，即這三個元素完全相等時，我們可以往后面找，找到一個和nums[i]不相同的元素為止，將這后面這一串往前挪，這里就要注意不同情況，當往后找的過程中如果找不到，那就應該直接返回i，例如nums=[1,1,1,1,1];如果找到了，我們移動的的時候也要注意，我們先定義個變量標記移動了多少位，然后進行賦值，賦值完后“數組的長度”其實也是分兩種情況的，例如nums=[1,1,1,1,1,2,3,4,5],我們移動后變成nums={1,1,2,3,4,5,3,4,5},但是我們應該只取前6位，例如nums={1,1,1,1,1,2},我們移動后變成nums={1,1,2,1,1,2},但是我們應該只取前2位；這就是兩只不同情況，具體大家可以結合下面圖示和代碼仔細揣摩一下。所以我們移動完后，要改變遍歷的數組長度，直至遍歷結束，i就是需要返回的數組長度。

思路二：上述我們其實貌似不用這么復雜，我們定義兩個指針n,i，一個負責往后遍歷，一個記錄當前“新數組“需要存放的最新位置，當往后遍歷的過程中發現當索引下標的值不等于前面第二個元素時，則將數組記錄需要存放的最新位置設置成當前元素,以此類推返回i即為數組長度，大家可以結合如下代碼仔細思考一下，再嘗試著自己去實現。

刪除排序數組中的重復項

MR.Zhu，公眾號：1024和996刪除排序數組中的重復項代碼實現/** * leetcode 80 */public class Solution { /** * 方法一 * * @param nums * @return */ public int removeDuplicates(int[] nums) { if (nums == null || nums.length == 0) { return 0; } if (nums.length < 3) { return nums.length; } int i = 2; int length = nums.length; while (i < length) { if (nums[i] == nums[i - 2]) { int flag = i; int point = i; while (point + 1 != length && nums[point] == nums[point + 1]) { point++; } //沒找到，則返回 if (point + 1 == length) { return i; } //移動賦值 for (int j = point + 1, k = 0; j < length; j++, k++) { nums[flag + k] = nums[j]; } //判斷有效長度 if (length - point - 1 < point - i) { length = i + (length - point - 1); } else { length = length - (point + 1 - i); } } i++; } return i; } /** * 方法二 * @param nums * @return */ public int removeDuplicates2(int[] nums) { int i=0; for(int n:nums){ if(i<2){ i++; continue; } if(n!=nums[i-2]){ nums[i]=n; i++; } } return i; } public static void printArr(int[] arr) { for (int num : arr) { System.out.print(num + "\t"); } System.out.println(); } public static void main(String[] args) { int nums[] = { 0, 1, 1, 1, 1, 2, 3, 3, 3, 4 }; System.out.println("方法一刪除重復項后數組長度:" + new Solution().removeDuplicates(nums)); System.out.println("方法一刪除重復項后數組為:"); printArr(nums); int nums2[] = { 0, 1, 1, 1, 1, 2, 3, 3, 3, 4 }; System.out.println("方法二刪除重復項后數組長度:" + new Solution().removeDuplicates2(nums2)); System.out.println("方法二刪除重復項后數組為:"); printArr(nums2); }}運行結果

總結

以上是生活随笔為你收集整理的vue删除数组中的一条数据_删除排序数组中的重复项 II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。