[LeetCode mobile zero] | punch brush

Question 12, I wanted to send a big trick, but time is limited, the question bank did not brush particularly difficult double pointer problem, to a move 0 problem to relax!

Has been the habit of brush, recently saw the nuggets held a brush activities, especially to participate in! This topic is question 12. I have to say the nuggets theme is beautiful! Praise.

This article is participating in the nuggets team online activity, clickCheck spring recruitment positions in big factories

I. Title Description:

Mobile zero

Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements.

Example:

Case 1:

Input: nums = [0, 1, 0, 3, 12], output: [1, 3, 12, 0, 0].Copy the code

Example 2:

Input: nums = [0, 0, 0, 3, 1], output: [3, 1, 0, 0, 0].Copy the code

Example 3:

Input: [0,1,0,3,12] output: [1,3,12,0,0]Copy the code

Note: must operate on the original array, cannot copy additional arrays. Minimize the number of operations.

Ii. Analysis of Ideas:

methods
describe
Time complexity
Spatial complexity
Double pointer Same direction double pointer, two ways to do it
O ( n ) O(n)
( 1 ) (1)
The first step leftRecord the new array,rightRecord the old array,
O ( n ) O(n)
( 1 ) (1)
The second step Iterate over the old array, moverightPointer, the old array is not0.leftandrightAt the same time mobile
O ( n ) O(n)
( 1 ) (1)
The third step The old array for0Alone,rightMobile,leftRecorded as0The location of the
O ( n ) O(n)
( 1 ) (1)
The fourth step The old array does not0, there are two approaches:

Method 1: willrightandleftThe values of,leftandrightAt the same time mobile
O ( n ) O(n)
( 1 ) (1)
Step 5 Method 2: willrightAssigns the value toleftThe position, at the end of the traversal, will be[0... left right] that...In theleft->rightBetween the0Is rewritten as0
O ( n ) O(n)
( 1 ) (1)

Iii. AC Code:

Way1 and way2 are already open in comments

// @lc code=start
class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        int right = 0;
        // ways 1:
        // while (right < nums.length) {
        // if (nums[right] ! = 0) {
        // int temp = nums[left];
        // nums[left] = nums[right];
        // nums[right] = temp;
        // left++;
        // }
        // right ++;
        // }
        // way 2
        while (right < nums.length) {
            if(nums[right] ! =0) {
                if(left ! = right) { nums[left] = nums[right]; } left++; } right++; }while (left < nums.length) {
            if(nums[left] ! =0) {
                nums[left] = 0; } left++; }}}// @lc code=end

Copy the code

Iv. Summary:

This time, the left and right point to two arrays. The difference is:

  • Idea 1 is to create a temporary array,The for loopAt a time
  • Idea 2 is to abstract a nonexistent array from the original arrayThe while loopTwice, the first timeleftRecord not for0The second time fromnums[left]So let’s start by setting all the non-zero elements to zero0