Question
Formatted question description: https://leetcode.ca/all/26.html
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 nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.
@tag-array
Algorithm
Use fast and slow pointers to record the traversed coordinates. At the beginning, both pointers point to the first number. If the two pointers point to the same number, the fast pointer will move forward. If they are different, both pointers will move forward. One step, so that when the fast pointer goes through the entire array, the current coordinate of the slow pointer plus 1 is the number of different numbers in the array.
Code
Java
-
// same thing, two pointers public class Remove_Duplicates_from_Sorted_Array { public class Solution { public int removeDuplicates(int[] nums) { if(nums == null || nums.length == 0) { return 0; } int i = 0; // slow pointer int j = 0; // fast pointer while(j < nums.length) { while(j + 1< nums.length && nums[j] == nums[j + 1]) { j++; } nums[i] = nums[j]; i++; j++; } return i; // i is incremented, but is index. So same as length } } }
-
// OJ: https://leetcode.com/problems/remove-duplicates-from-sorted-array/ // Time: O(N) // Space: O(1) class Solution { public: int removeDuplicates(vector<int>& A) { int j = 0; for (int n : A) { if (j - 1 < 0 || A[j - 1] != n) A[j++] = n; } return j; } };
-
class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) <= 1: return len(nums) slow = 0 for i in range(1, len(nums)): if nums[i] != nums[slow]: slow += 1 nums[slow] = nums[i] return slow + 1