# Remove Duplicates from Sorted Array II ### Source - leetcode: [Remove Duplicates from Sorted Array II | LeetCode OJ](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/) - lintcode: [(101) Remove Duplicates from Sorted Array II](http://www.lintcode.com/en/problem/remove-duplicates-from-sorted-array-ii/) ~~~ Follow up for "Remove Duplicates": What if duplicates are allowed at most twice? For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3]. Example ~~~ ### 題解 在上題基礎上加了限制條件元素最多可重復出現兩次。~~因此可以在原題的基礎上添加一變量跟蹤元素重復出現的次數，小于指定值時執行賦值操作。但是需要注意的是重復出現次數`occurence`的初始值(從1開始，而不是0)和reset的時機。~~這種方法比較復雜，謝謝 @meishenme 提供的簡潔方法，核心思想仍然是兩根指針，只不過此時新索引自增的條件是當前遍歷的數組值和『新索引』或者『新索引-1』兩者之一不同。 ### C++ ~~~ class Solution { public: /** * @param A: a list of integers * @return : return an integer */ int removeDuplicates(vector<int> &nums) { if (nums.size() <= 2) return nums.size(); int len = nums.size(); int newIndex = 1; for (int i = 2; i < len; ++i) { if (nums[i] != nums[newIndex] || nums[i] != nums[newIndex - 1]) { ++newIndex; nums[newIndex] = nums[i]; } } return newIndex + 1; } }; ~~~ ### Java ~~~ public class Solution { /** * @param A: a array of integers * @return : return an integer */ public int removeDuplicates(int[] nums) { if (nums == null) return -1; if (nums.length <= 2) return nums.length; int newIndex = 1; for (int i = 2; i < nums.length; i++) { if (nums[i] != nums[newIndex] || nums[i] != nums[newIndex - 1]) { newIndex++; nums[newIndex] = nums[i]; } } return newIndex + 1; } } ~~~ ### 源碼分析 遍歷數組時 i 從2開始，newIndex 初始化為1便于分析。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 空間復雜度 O(1)O(1)O(1).