题目
https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/28/
个人解法
测试用例数(个) | 执行用时(ms) | 战胜 |
---|---|---|
21 | 96 | 98.75% |
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
var unZeroIndex = 0;
for (var i = 0 ; i < nums.length ; i++) {
if (nums[i] !== 0) {
nums[unZeroIndex] = nums[i];
unZeroIndex++;
}
}
for (var i = nums.length - 1 ; i >= unZeroIndex ; i--) {
nums[i] = 0;
}
return nums;
};
最快解法
测试用例数(个) | 执行用时(ms) | 战胜 |
---|---|---|
21 | 64 | 100% |
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
var zeroCount = 0;
for(var i=0; i<nums.length; i++){
if(nums[i]==0){
zeroCount ++;
}else if(zeroCount>0){
nums[i-zeroCount]=nums[i];
nums[i] = 0;
}
}
};
分析
「个人解法」时间复杂度为 O(2n),「最快解法」时间复杂度为 O(n)。特别是当数组全为零时,「个人解法」性能最差。
「最快解法」是将非零元素与第一个零元素进行交换。分解过程如下,以 [0,1,0,3,12]
为例:
[0,1,0,3,12]
--> 0,1交换
[1,0,0,3,12]
--> 0,3交换
[1,3,0,0,12]
--> 0,12交换
[1,3,12,0,0]
-->