第 82 题：算法题「移动零」，给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

Question

示例：

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

说明：

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

Answer 1

 function moveZero(arr) {
        if (!arr instanceof Array || arr.length <= 0) return arr
        let zeroIndex = -1;
        let i = 0;
        while (i < arr.length) {
            if (arr[i] !== 0 && zeroIndex >= 0) {
                swap(i, zeroIndex, arr)
                zeroIndex++
            } else if (arr[i] === 0 && zeroIndex < 0) {
                zeroIndex = i
            }
            i++
        }
        return arr
    }

    function swap(i, j, arr) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    const arr = [0, 1, 0, 3, 12]
    console.log(moveZero(arr))

原地交换，没有用多余的数组。应该是O（n）。
木有上面大佬的简洁，不知道能不能覆盖所有情况，求指正

Answer 2

const array = [2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
// array = [ 2, 1, 4, 5, 7, 8, 0, 0, 0, 0 ]

这里有个问题，首元素为0无效，不知道为什么，求教

const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
console.log(array);
// array = [ 8, 7, 1, 4, 2, 5, 0, 0, 0, 0, 0 ]

这个我在 chrome 上试的时候无法排序，在 safari 上倒是可以按照逻辑输出 @wz71014q

Answer 3

上面所有的再循环中，先splice在推的方法都是有问题的
因为，当splice一个元素的时候，紧跟着的后面一个元素会向前移动一位，索引会变成正在删除那个元素的，所有当有连续的​​0时候，无法满足要求

那个这个问题怎么解决？没头绪

还用上面的方法的话，如果元素为0，可以把正在循环的索引减 1

Answer 4

const array = [2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
// array = [ 2, 1, 4, 5, 7, 8, 0, 0, 0, 0 ]

这里有个问题，首元素为0无效，不知道为什么，求教

const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
console.log(array);
// array = [ 8, 7, 1, 4, 2, 5, 0, 0, 0, 0, 0 ]

这个我在 chrome 上试的时候无法排序，在 safari 上倒是可以按照逻辑输出 @wz71014q

const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
return (fir === 0) ? 1 : -1
})

这样试试？

如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明>这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b，其返回值如下：

若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
若 a 等于 b，则返回 0。
若 a 大于 b，则返回一个大于 0 的值。

Answer 5

可以了，谢啦 @lo1412

Answer 6

clock in

Answer 7

思路：

1. 先把数组中的0全部去掉
2. 对比初始数组和去掉0后的数组的长度
3. 长度相差多少就在数组末尾添加几个0

const result = (arr) => arr.filter(Boolean).concat([...Array(arr.length - arr.filter(Boolean).length).fill(0)])
result([0,1,0,3,0,12,0])    // [1, 3, 12, 0, 0, 0, 0]

Answer 8

@kingstone3 我用node运行的是可以，后面放到chrome果然结果不一样。。。没有safari。。。没有试具体结果

// 换成这样后，在chrome第一次是输出全部相反的顺序，再运行一次sort，才会把顺序变回来
const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
    return (fir === 0) ? 1 : -1
})

Answer 9

// 应该也是对的
const moveZero = (arr) => {
  arr.forEach(() => {
    let index = arr.indexOf(0);
    if (index !== -1) {
      let slice = arr.splice(index, 1);
      arr.push(...slice);
    }
  });
  return arr;
};

console.log(moveZero([0, 1, 0, 0, 0, 3, 12]));

Answer 10

let arr = [0, 1, 0, 0, 0, 3, 12];
let count = 0;
for (let i = 0; i < arr.length; i++) {
  if (arr[i] === 0) {
    arr.splice(i, 1);
    i--;
    count++;
    arr.push(null);
  }
}
for (let i = (arr.length - count); i < arr.length; i++) {
  arr[i] = 0;
}
console.log(arr);

Answer 11

const moveZeros = function (arr) {
  return [
    ...(arr.filter(n => n !== 0)),
    ...(arr.filter(n => n === 0))
  ];
}

Answer 12

function moveZero(nums) {
    let index = 0
    let length = nums.length
    while (length) {
        if(nums[index] === 0){
            nums.splice(index, 1)
            nums.push(0)
        } else {
            index++
        }
        length --
    }
    return nums
}

Answer 13

var arr = [0, 1, 0, 3, 12];
for (let i = arr.length - 1; i >= 0; i--) {
if (arr[i] == 0) {
arr.splice(i, 1);
arr.push(0)
}
}

@tanggd
阁下觉得我的写法怎么样
流下没有技术的眼泪

Answer 14

示例:

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

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

arr.sort((a,b) => { if(Math.abs(a-b) == (a +b)){return b-a}})

Answer 15

var input = [0,1,0,0,3,12,0];
function moveZeroEnd(arr) {
  const zeroCount = arr.filter(i => i === 0).length;
  const zeroRemoved = arr.sort((a, b) => a - b).splice(0, zeroCount);
  return arr.concat(zeroRemoved);
}
console.log(moveZeroEnd(input))

Answer 16

function test1(arr) {
    let i = 0, pointer = 0;
    while (pointer < arr.length) {
        if (arr[i] == 0) {
            arr.splice(i, 1);
            arr.push(0);
        } else {
            i++;
        }
        pointer++;
    }
    return arr;
}

Answer 17

let j = 0;
for (let i = 0; i < arr.length - 1; i++) {
   if (arr[j] == 0) {
        arr.push(...arr.splice(j, 1));
    } else {
        j++
    }
}

Answer 18

var arr = [0,1,0,3,12,100,0,90,33,2,0,4];
arr.sort(function(a,b){
return (a == 0 || b == 0) ? b-a : a-b;
})
console.log(arr)

Answer 19

发现是零，continue，否则就填充数组，最后补零；

Answer 20

const moveZeros = (nums: number[]): number[] => {
return moveZerosR(nums, 0, nums.length - 1)
}

const moveZerosR = (nums: number[], l: number, r: number): number[] => {
if (l > r) return
const top = nums.shift()
if (top === 0) {
return [...moveZerosR(nums, l + 1, r), top]
} else {
return [top, ...moveZerosR(nums, l + 1, r)]
}
}

Answer 21

//先删除所有0，再添加到尾部就行了，len就是删除的0的个数
function moveZero(arr) {
	let len = 0;
	while (arr.includes(0)) {
		let index = arr.indexOf(0);
		arr.splice(index, 1);
		len++;
		}
	return arr.concat(new Array(len).fill(0));
}
console.log(moveZero([1, 0, 3, 0, 12, 5, 4, 3, 2, 0, 10, 2, 0, 9]));

Answer 22

let arr = [1,0,2,0,4,5];
        let num = 0;
        for(let i = 0;i<arr.length - num;i++) {
            if(arr[i] == 0) {
                arr.push(...arr.splice(i,1));
                i--;
                num++;
            }
        }
        console.log(arr)

Answer 23

let arr = [3, -2, 341, 4, 0, 0, 3, 531, 0, 0, 0, 13, 53]
function roll(arr) {
let i = 0, j = arr.length - 1;
while (i < j) {
if (arr[i] === 0) {
swap(arr, i, j);
j--;
}
i++
}
return arr
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp
}
console.log(roll(arr));

Answer 24

双指针，空间、时间复杂度都是最优

const move = (arr) => {
  const len = arr.length;

  let i = 0;
  let j = 0;

  while (i < len) {
    if (arr[i] !== 0) {
      arr[j] = arr[i];
      j++;
    }
    i++;
  }

  while (j < len) {
    arr[j] = 0;
    j++;
  }

  return arr;
};

Answer 25

function move (arr) { let k = arr.length - 1 while (k >= 0) { if (arr[k] === 0) { arr.push(arr.splice(k, 1)[0]) } k-- } return arr }

Answer 26

function zeroMove(arr){
    arr.sort((a,b) => a-b)
    let j = 0;
    for(i of arr){
        if(i === 0 && j < arr.length){
            arr.shift();
            arr.push(i);
            j++;
        }
    }
    return arr
}

Answer 27

利用排序，非0之间相等，0比非0大

function sort(nums){
    return nums.sort((a, b) => {
        if(a===0&&b!==0) return 1
        if(a!==0&&b===0) return -1;
        return 0
    })
}

Answer 28

function sort(arr){
let i=0;
let j=arr.length-1;
while(i<j){
while(arr[i]!==0){
i++;
}
while(arr[j]==0){
j--;
}
if(i<j){
let tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
return arr;
}

Answer 29

function fun(nums) {
  let j = nums.length
  for (let i = 0; i < j; i++) {
    if(nums[i]===0){
      nums.splice(i,1)
      nums.push(0)
      i--
      j--
    }
  }
  return nums
}
fun([0,0,1,0,3,12])

Answer 30

上面所有的再循环中，先 splice 在 push 的方法都是有问题的

因为，当splice 一个元素的时候，紧跟着的后面一个元素会向前移动一位，索引会变成正在删除那个元素的，所有当有连续的 0 时候，无法满足要求

Answer 31

const array = [2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
// array = [ 2, 1, 4, 5, 7, 8, 0, 0, 0, 0 ]

这里有个问题，首元素为0无效，不知道为什么，求教

const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
console.log(array);
// array = [ 8, 7, 1, 4, 2, 5, 0, 0, 0, 0, 0 ]

Answer 32

let moveZero = (arr) => {
let point = 0
for (var i = 0; i < arr.length; i++) {
if (arr[i]!=0) {
arr[point] = arr[i]
arr[i] = 0
point++
}
}

return arr
}

Answer 33

最优解法

想到好几个方法，楼上都写出来了，但是我觉得这些都不是最优解法，既然是算法题，自然是以算法的思维去解。

function moveZeroToLast(arr) {
    let index = 0;
    for (let i = 0, length = arr.length; i < length; i++) {
        if (arr[i] === 0) {
            index++;
        } else if (index !== 0) {
            arr[i - index] = arr[i];
            arr[i] = 0;
        }
    }
    return arr;
}

Answer 34

上面所有的再循环中，先splice在推的方法都是有问题的

因为，当splice一个元素的时候，紧跟着的后面一个元素会向前移动一位，索引会变成正在删除那个元素的，所有当有连续的​​0时候，无法满足要求

那个这个问题怎么解决？没头绪

Answer 35

const moveZeroToEnd = (arr) => {
    let index = 0
    let current = 0
    while(index < arr.length) {
        if (arr[current] === 0) {
            arr.splice(current, 1)
            arr.push(0)
        } else {
            current++
        }
        index++
    }
    return arr
}

Answer 36

//倒序循环可避免
const arr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 0, 1, 9, 9, 9, 0, 0, 0, 0, 1, 0, 3, 12, 0, 0, 0, 0];
    const len = arr.length;
    console.log(len)
    for (let i = len; i >= 0; i--) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        arr.push(0)
      }
    }
    console.log(arr)

Answer 37

//倒序循环可避免
const arr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 0, 1, 9, 9, 9, 0, 0, 0, 0, 1, 0, 3, 12, 0, 0, 0, 0];
    const len = arr.length;
    console.log(len)
    for (let i = len; i >= 0; i--) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        arr.push(0)
      }
    }
    console.log(arr)

为什么倒序可以解决这个办法

Answer 38

//倒序循环可避免
const arr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 0, 1, 9, 9, 9, 0, 0, 0, 0, 1, 0, 3, 12, 0, 0, 0, 0];
    const len = arr.length;
    console.log(len)
    for (let i = len; i >= 0; i--) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        arr.push(0)
      }
    }
    console.log(arr)

为什么倒序可以解决这个办法

因为待处理的数据索引没有变。https://www.jianshu.com/p/77247e9e1849

Answer 39

• 首先，题意是要在原地修改数组，那么sort，concat之类的纯函数方法就是行不通的了，因为是返回新的数组，而不是在原地修改
• 其次，splice的时间复杂度是O(n)，那么使用splice的算法的时间复杂度是O(n2)，既然在写算法，那么就要寻求时间复杂度与空间复杂度最低的办法。

---

思路：双指针

• 设定一个慢指针一个快指针，快指针每次+1， 当慢指针的值不等于0的时候也往后移动，当慢指针等于0并且快指针不等于0的时候，交换快慢指针的值，慢指针再+1

function moveZero(arr) {
  let i = 0
  let j = 0
  while (j < arr.length) {
    if (arr[i] !== 0) {
      i++
    } else if (arr[j] !== 0) {
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
      i++
    }
    j++
  }
}

时间复杂度O(n)，n是数组长度，空间复杂度O(1)

Answer 40

//最后有啥办法不循环么，直接截取放最后
var arr = [0,1,0,3,12,0,89,0,8,0] ;

function ss (arr){
    arr.sort((a,b)=>{
        return a-b
    });
    let len = arr.lastIndexOf(0) +1;
    arr.splice(0,len);
    for (let i=0;i<len;i++){
        arr.push(0)
    }
    console.log(arr)
}
ss(arr)

Answer 41

// 正序循环方案
// 由于splice会将nums.length - 1，所以让数组下标自减，强制回溯到上一个已操作的元素
const moveZeroToEnd = (nums) => {
	let length = nums.length
	for (let i = 0; i < nums.length; i++) {
		let el = nums[i]
		if (el === 0) {
			nums.splice(i, 1)
			i--
		}
	}
	let tmpAry = new Array((length - nums.length)).fill(0)
	return [...nums, ...tmpAry]
}
moveZeroToEnd([1,2,0,0,0,0,0,0,3,0,4])

Answer 42

思路是把0剔除出来，然后再塞进去- -

function moveZero(arr) {
      let num = 0
      let index = -1
      while ((index = arr.indexOf(0)) > -1) {
        num++
        arr.splice(index, 1)
      }

      while (num--) {
        arr.push(0)
      }
}

Answer 43

let or = [0, 1, 0, 3, 12]
let len = or.length
while (len) {
if(!or[len-1]){
or.push(...or.splice(len-1,1))
}
len --
}
console.log(or) // [1, 3, 12, 0, 0]

Answer 44

function move (arr) {
let counter = 0
for (let index = 0; index < arr.length; index++) {
const item = arr[index];
if (item === 0) {
arr.splice(index, 1)
counter++
index--
}
}
arr.push(...new Array(counter).fill(0))
return arr
}

Answer 45

function sortArr(arr) {
    let arrLength = arr.length;
    for (let i = 0; i < arrLength; i++) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        i--;
        arrLength--;
        arr.push(0);
      }
    }
    return arr;
  }

Answer 46

已修正连续多个 0 时的 bug
思路：用一个 len 记录 0 的出现次数，再过滤掉原数组中所有的 0，最后在数组末尾补上被移除的 0

let nums = [0, 0, 0, 1, 0, 3, 12];

console.log(moveZeroToLast(nums));  // [1, 3, 12, 0, 0, 0, 0]

function moveZeroToLast(arr) {
  let len = arr.length;

  return arr.filter(it => it === 0 ? len-- && false : true)
    .concat(Array(arr.length - len).fill(0));
}

Answer 47

function move(arr){ 
  var n = 0; 
  for(var i = 0; i < arr.length; i++){ 
    if(arr[i] === 0){ 
       arr.splice(i, 1);
       n++; 
       i--; 
    }
  } 
  while(n--){ 
    arr.push(0); 
  }
  return arr;
}

Answer 48

let arr = [1,2,3,0,7,0]
j = arr.length
for (i = 0; i < j; i++) {
if (arr[i] === 0) {
arr.splice(i,1)
arr.push(0)
}
}

Answer 49

let nums = [0,1,0,3,12];

for (let i = 0; i < nums.length; i++){
  if (nums[i] === 0){
    nums.push(0);
    nums.splice(i,1);
  }
};

Answer 50

        const moveZore = (arr) => {
            let n = 0
            arr.forEach((item, index) => {
                if (item === 0){
                    arr.splice(index, 1)
                    n++;
                }
            })
            arr.push(...(new Array(n)).fill(0))
            return arr;
        }

Answer 51

新增：解决了有连续的0无法实现功能的问题。

function zeroMove(array) {
        let len = array.length;
        let j = 0;
        for(let i=0;i<len-j;i++){
            if(array[i]===0){
                array.push(0);
                array.splice(i,1);
                i --;
                j ++;
            }
        }
        return array;
    }