Tags: Two Pointer

Topic:

26. Delete duplicates in sorted array -> Link

Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array.

Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.

Example 1:

Given the array nums = [1,1,2], the function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. You don't need to worry about the element after the new length in the array.Copy the code

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4], the function should return a new length of 5, and the first five elements of the original nums array are modified to 0,1, 2,3, 4. You don't need to worry about the element after the new length in the array.Copy the code

Description:

Why is the return value an integer, but the output answer is an array?

Note that the input array is passed “by reference”, which means that modifying the input array within the function is visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, it does not make any copies of the arguments int len = removeDuplicates(nums); // Modifying the input array in a function is visible to the caller. // Depending on the length returned by your function, it prints out all elements in the array within that length. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the code

Subject analysis

In this case, it involves the idea of in situ, an algorithm that uses a small, fixed amount of extra space to convert data. When the algorithm is executed, the input data is usually overwritten by the output.

If you don’t care, this problem can easily be rewritten using Set or Hash. But using sets and hashes opens up new memory. To increase space complexity, we can use the double pointer method here.

  1. First, check that the array passed is not empty and the length is greater than one.
  2. Define a new array length newLength, starting from 0, slow pointer;
  3. Iterate over the number group, define the fast pointer I;
  4. When num[I] == num[newLength], the slow pointer newLength remains unchanged, and the fast pointer I +1. Skip duplicates.
  5. When num [I]! = num[newLength], slow newLength+1, fast pointer I +1, nums[newLength] = nums[I].
  6. Repeat the process until the end of the loop.

Complexity analysis

  • Time complexity:O(n), suppose the array has a total ofnI and j are at least iterated2nStep.
  • Space complexity: O(1).

Java

class Solution {
    public int removeDuplicates(int[] nums) {
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int newLength = 1;
           
        for (int i = 1; i<nums.length; i++) {
            
            if (nums[i] != nums[i-1]) {
                nums[newLength++] = nums[i];
            }
        }
        return newLength;    
    }
}
Copy the code

Swift

func removeDuplicates(_ nums: inout [Int]) -> Int { guard nums.count > 0 else { return 0 } var newLength = 1; for idx in 1 .. < nums.count { if nums[idx] ! = nums[idx - 1] { nums[newLength] = nums[idx] newLength += 1 } } return newLength }Copy the code

JavaScript

var removeDuplicates = function(nums) { if (nums === 'undefined' || nums.length === 0) { return 0 } var i = 1; for (var j = 1; j < nums.length; j++) { if (nums[j] ! = nums[j - 1]) { nums[i] = nums[j]; i++; } } return i; };Copy the code