菜单 学习猿地 - LMONKEY

php 解题leetcode 282 移动零

UvDream profile image UvDream ・1 min read

课程推荐:PHP开发工程师--学习猿地精品课程

题目描述
leetcode 282 问题,数组问题

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
说明:

必须在原数组上操作,不能拷贝额外的数组。

尽量减少操作次数

测试样例

输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

输入: [0,1]

输出: [1,0]

输入: []

输出: []

方案

方案1:

做两次遍历,第一次遍历,假若有m个非0元素,将所有非0元素填充到数组前m个位置,记录下数量m。

第二次遍历从m开始到数组最后一个n,全部填充0;

代码实现

php

function moveZeroes($nums){
$len = count($nums);
$flag = 0;
for($i=0;$i<$len;$i++) {
if($nums[$i] != 0) {
$nums[$flag] = $nums[$i];
$flag++;
}
}
for($i=$flag;$i<$len;$i++){
$nums[$i] = 0;
}
return $nums;
}
js

var moveZeroes = function(nums) {
var zIndex = 0;
var len = nums.length;
for(var i=0;i<len;i++){
if(nums[i]!=0){
var tmp = nums[i];
nums[i] = nums[zIndex];
nums[zIndex] = tmp;
zIndex++;
}
}
};
方案2:

进行一次遍历,调换0元素与非0元素之间的位置,添加一个游标$flag,记录数组中第一个0元素的位置,如果$i个元素不等于0,$nums[$flag]与$nums[$i]位置互换,$flag 加一,遍历完后,所有的非0元素替换到数组的前面。

[0........$flag)这个区间是非0元素

[$flag.....$i)这个区间是0元素

[$i.......$n-1]待遍历元素

遍历演示

[0,1,0,3,12] $i = 0 $flag=0;

[1,0,0,3,12] $i = 1 $flag=1;

[1,0,0,3,12] $i = 2 $flag=1;

[1,3,0,0,12] $i = 3 $flag=2;

[1,3,12,0,0] $i = 4 $flag=3;

代码:

php

//交换函数
function _swap(&$arr,$a,$b){
$arr[$a] ^= $arr[$b];
$arr[$b] ^= $arr[$a];
$arr[$a] ^= $arr[$b];

}

function moveZeroes($nums){
$len = count($nums);
$flag = 0;
for($i=0;$i<$len;$i++) {
if ($nums[$i] != 0) {
if ($i != $flag) {
_swap($nums, $i, $flag);
}
$flag++;
}
}
return $nums;
}
js

var moveZeroes = function(nums) {
//交换函数
var _swap = function(arr,a,b){
arr[a] ^= arr[b];
arr[b] ^= arr[a];
arr[a] ^= arr[b];
}
var flag = 0;
var len = nums.length;
for(var i=0;i<len;i++){
if(nums[i]!=0){
if(i!=flag){
_swap(nums,i,flag)
}
flag++;
}
}
};

文章来自:https://zhuanlan.zhihu.com/p/43192120

评论 (0)