Array - fast and slow pointer in one breath

Preface

　　 The last article talked about differential arrays , This article begins with the fast and slow pointer technique of the double pointer technique . in addition , The array has the following knowledge points and skills .

Ideas

　　 Manipulate an array with two pointers , Usually used in ：1. When there are changes to the array and a new array cannot be created .2. A traversal of the implementation requirements .
　　 in addition , Double pointer types have fast and slow pointers , Left and right pointer , Sliding window , Common type .
Speed pointer template

int  Slow pointer  = 0;
for (int  Quick pointer  = 0; fast < nums.length;  Quick pointer ++) {
    if ( The fast pointer satisfies a condition ) {
         Slow pointer assignment operation 
         Slow pointer right movement operation 
    }
}

Remove duplicate items from an ordered array

leetcode The first 26 topic Their thinking
　　 Apply template ,“ The fast pointer satisfies one of the conditions ”： The speed pointer refers to different elements . 　　 When the last value is returned , Need to set the slow pointer +1.
Complexity analysis
　　 Time complexity ：O(n),n Is the length of the array . 　　 Spatial complexity ：O(1).
Code

class Solution {
    public int removeDuplicates(int[] nums) {
      int slow = 0;
      for (int fast = 0; fast < nums.length; fast++) {
         // The element indicated by the speed pointer does not work 
         if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
         }
      }
      return slow + 1;
    }
}

Remove elements

leetcode The first 27 topic Their thinking
　　 Apply template ,“ The fast pointer satisfies one of the conditions ”： Indicates that the element indicated by the fast pointer is different from the given value .
Complexity analysis
　　 Time complexity ：O(n),n Is the length of the array .
　　 Spatial complexity ：O(1).
Code

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            // The element indicated by the fast pointer is related to val Different 
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

Move zero

leetcode The first 283 topic Their thinking
　　 Apply template ,“ The fast pointer satisfies one of the conditions ”： The element indicated by the fast pointer is not equal to 0.
　　 Finally, we traverse the array from the slow pointer , Assign values to all elements traversed 0.
Complexity analysis
　　 Time complexity ：O(n),n Is the length of the array .
　　 Spatial complexity ：O(1).
Code

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        // Assign the full pointer and the following position to 0
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

ending

　　 The speed pointer of the array is relatively simple , In addition, linked lists also have fast and slow pointer skills . The next algorithm article talks about the left and right pointers of double pointers .

Wechat scan the QR code below , Or search for “xicheng”, Pay attention to the official account 【 note 】, I have prepared 15 swastika Java Interview notes .

　　 Thank you for your praise 、 Collections and reviews , Dry goods articles are continuously updated , See you in the next article ！