一、题目
LeetCode-283. 移动零
链接：https://leetcode-cn.com/problems/move-zeroes/
难度：简单
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
二、解题思路
方法一： 指针
创建两个指针slow和fast分别指向数组的一个元素，fast从左向右遍历，如果指向的元素不为0，交换两个指针指向元素的值，并且slow++。
方法二：直接覆盖
个人觉得方法二更好理解一些，创建一个索引index = 0，从左向右遍历，将不为零的元素赋值给nums[index]，index++。最后将剩余位置补0。
三、实现过程
方法一： 指针
c++
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0, fast = 0;
while(fast < nums.size()){
if(nums[fast]){
swap(nums[fast],nums[slow]);
slow++;
}
fast++;
}
}
};
PHP
class Solution {
/**
* @param Integer[] $nums
* @return NULL
*/
function moveZeroes(&$nums) {
$slow = 0;
$fast = 0;
$len = count($nums);
while($fast < $len){
if($nums[$fast]){
$temp = $nums[$slow];
$nums[$slow] = $nums[$fast];
$nums[$fast] = $temp;
$slow++;
}
$fast++;
}
}
}
JavaScript
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let slow = 0,fast = 0,len = nums.length;
while(fast < len){
if(nums[fast]){
let temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
fast++;
}
};
方法二：直接覆盖
c++
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int index = 0;
for(int i = 0; i < nums.size();i++){
if(nums[i]){
nums[index++] = nums[i];
}
}
for(;index < nums.size();index++){
nums[index] = 0;
}
}
};
PHP
class Solution {
/**
* @param Integer[] $nums
* @return NULL
*/
function moveZeroes(&$nums) {
$index = 0;
$len = count($nums);
for($i = 0; $i < $len;$i++){
if($nums[$i]){
$nums[$index++] = $nums[$i];
}
}
for(;$index < $len;$index++){
$nums[$index] = 0;
}
}
}
JavaScript
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
var index = 0;
for(let i = 0; i < nums.length;i++){
if(nums[i]){
nums[index++] = nums[i];
}
}
for(;index < nums.length;index++){
nums[index] = 0;
}
};
四、小结
- 时间复杂度：O(N)，其中N是数组的长度。
- 空间复杂度：O(1)，只需要使用常数的额外空间。
