Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

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.

The sample

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

prompt

  1. Must operate on the original array, cannot copy additional arrays.
  2. Minimize the number of operations.

Their thinking

Double pointer

Operations must be performed on the original array and the number of operations must be minimized. We can’t use the extra space to save the result quickly. We can only move the pointer so that the next value moves to the front. At the same time, we need to record the number of elements 0 in the array, so that we can calculate the movement interval when the elements move.

class Solution {
    public void moveZeroes(int[] nums) {
        // zeroCount records the number of elements 0
        int n = nums.length, zeroCount = 0;

        for(int i = 0; i < n; ++i){
            // The current element is 0 and the interval is +1
            if(nums[i] == 0){
                ++zeroCount;
            }else{
                // The current element is not 0, zeroCount bit forward, based on the preceding 0 element to determine the specific forward positionnums[i - zeroCount] = nums[i]; }}// Change all subsequent elements to 0
        for(int i = n - zeroCount; i < n; ++i){
            nums[i] = 0; }}}Copy the code

Complexity analysis

  • Time complexity: O(N)O(N)O(N)
  • Space complexity: O(1)O(1)O(1)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/mo…