# Remove Duplicates from Sorted Array ### Source - leetcode: [Remove Duplicates from Sorted Array | LeetCode OJ](https://leetcode.com/problems/remove-duplicates-from-sorted-array/) - lintcode: [(100) Remove Duplicates from Sorted Array](http://www.lintcode.com/en/problem/remove-duplicates-from-sorted-array/) ~~~ Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2]. Example ~~~ ### 題解 使用兩根指針(下標)，一個指針(下標)遍歷數組，另一個指針(下標)只取不重復的數置于原數組中。 ### C++ ~~~ class Solution { public: /** * @param A: a list of integers * @return : return an integer */ int removeDuplicates(vector<int> &nums) { if (nums.size() <= 1) return nums.size(); int len = nums.size(); int newIndex = 0; for (int i = 1; i< len; ++i) { if (nums[i] != nums[newIndex]) { 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 <= 1) return nums.length; int newIndex = 0; for (int i = 1; i < nums.length; i++) { if (nums[i] != nums[newIndex]) { newIndex++; nums[newIndex] = nums[i]; } } return newIndex + 1; } } ~~~ ### 源碼分析 注意最后需要返回的是索引值加1。 ### 復雜度分析 遍歷一次數組，時間復雜度 O(n)O(n)O(n), 空間復雜度 O(1)O(1)O(1).