课程推荐: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++;
}
}
};
© 著作权归作者所有
发表评论