History of LeetCode

  • Algorithm Notes | LeetCode 349. Intersection of two arrays – easy
  • Algorithm Notes | LeetCode 14. Longest public prefix – easy
  • Algorithm Notes | LeetCode 1. Sum of two numbers – easy

GitHub address:

  • Github.com/HLQ-Struggl…

283. Move the 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:

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

Description:

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

A violent solution

Intuitively, the two-pointer solution is still adopted. I is used to traverse the entire NUMS array, and J is used to obtain the index that is not equal to 0 based on I, and replace the numbers of I and J with temporary variables.

The code is as follows:

fun moveZeroes(nums: IntArray): Unit { if (nums.isEmpty()) { return } for (i in nums.indices) { if (nums[i] == 0) { for (j in i until nums.size) { if (nums[j] ! = 0) { var tempNum = nums[i] nums[i] = nums[j] nums[j] = tempNum break } } } } }Copy the code

Execution consumption:

Two, stealthily replace the pillar method

I saw a nice solution on the Internet, and the general idea is as follows:

Still based on double Pointers, I is responsible for traversing the entire NUMS array; J is responsible for plugging values not equal to 0 into the current nums[j] position. Then change the number from j to nums.size to 0.

Of course, my description may have some problems, look at the code:

fun moveZeroes1(nums: IntArray): Unit { if (nums.isEmpty()) { return } var j = 0 for(i in nums.indices){ if(nums[i] ! = 0){ nums[j++] = nums[i] } } while (j < nums.size){ nums[j++] = 0 } }Copy the code

Execution consumption:

The following is a recommended example of LeetCode for your reference.

An example that takes 204 ms to execute

fun moveZeroes(nums: IntArray): Unit { var pointA = 0 var pointB = 0 while (pointB < nums.size) { val numB = nums[pointB] if (numB ! = 0) { nums[pointB] = nums[pointA] nums[pointA] = numB pointA++ } pointB++ } }Copy the code

Execute the example that consumes 35048 KB of memory

fun moveZeroes(nums: IntArray): Unit { var a = 0 var b = 0 while (b < nums.size) { if (nums[b] ! = 0) { nums[a] = nums[b] if (b > a) { nums[b] = 0 } a++ } b++ } }Copy the code