26. Remove duplicates from sorted array

Analysis of the

Because we might have duplicate elements in the array, and we want to skip over those duplicate elements, we need a pointer to move back; If you find a non-repeating element, you have to assign that element to the previous new array, so you also need a pointer.

So we use the fast and slow double pointer to solve the problem.

Obviously, a pointer that skips repeating elements backwards is a fast pointer, denoted by cur. The slow pointer we can represent as I going through the old array.

Let’s look at this test case:

0, 0, 1, 1, 2, 2, 3, 3, 4

Starting with index 1, determine if it is the same as the previous element. If it is, I does not move and cur moves back to find the first non-repeating element:

  1. I points to index 1 and cur points to index 2
  2. Perform assignment:nums[i] = nums[cur++]
  3. When you’re done, cur moves back, and then you go into the next cycle, and I moves back as well

If cur reaches the end of the array and still doesn’t find a unique element, it simply returns I, representing the size of the new array.

The following case

1 2 3

code

class Solution {
    public int removeDuplicates(int[] nums) {
        int cur = 1; / / pointer
        int i = 1; // Slow pointer to the size of the new array

        for (; i < nums.length; i++) {
            if (cur == nums.length) {
                return i; // When fast pointer traversal is complete, return I directly
            }

            If the fast pointer moves to the end of the array, all elements following the new array are the same. Return I */
            while (nums[cur] == nums[i - 1]) {
                if (++cur == nums.length) {
                    returni; }}Cur is the first non-repeating element to be added to the new array
            nums[i] = nums[cur++];
        }

        returni; }}Copy the code