跟我一起刷leetCode算法题7之 Move Zeroes
2017-08-03 本文已影响65人
打铁大师
283. Move Zeroes
这是leetCode第283题
题目
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
1.You must do this in-place without making a copy of the array.
2.Minimize the total number of operations.
意思是说:
给一个数字数组,写出一个函数把所有的0都移到数组的末尾,同时要保持非零的数字相对顺序不变。
给个例子,给出数组[0,1,0,3,12],调用函数之后,数组应该是这个样子的[1,3,12,0,0]。
注意:
1.你必须在原数组上操作,不能复制数组。
2.你的操作总数必须最小化
思路
1.先把所有非零数组都放在数组前面,并记录非零数字的数量n
举个例子:
给出数组 nums=[1,2,0,3,0,4] n=0表示非零数字数量
第一步:循环数组,当遇到非零数字时,nums[n]的位置赋值为该数字。
i = 0 nums=[1,2,0,3,0,4] 1仍然在原来的位置 n=>1
i = 1 nums=[1,2,0,3,0,4] 2仍然在原来的位置 n=>2
i = 2 nums=[1,2,0,3,0,4] 不变
i = 3 nums=[1,2,3,3,0,4] nums [n] =nums[ i ] n=>3
i = 4 nums=[1,2,3,3,0,4] 不变
i = 5 nums=[1,2,3,4,0,4] nums [n] =nums[ i ] n=>4
这样,就将所有非零数字都放在了数组开头。
2.将数组第n个位置之后的数字都重新赋值为0(因为非零数字都在n+1个位置之前);
最后得到结果:nums=[1,2,3,4,0,0]
代码如下:
/**
* @param {number[]} nums
* @return {void}
*/
var moveZeroes = function (nums) {
var count =0;
var l = nums.length;
for(var i=0;i<l;i++){
if(nums[i]!==0){
nums[count++]=nums[i]
}
}
for(;count<l;count++){
nums[count]=0;
}
}