将数组中的0移动到末尾

发表于 更新于 分类于
将数组中的0移动到末尾

题目如下

  • 将数组中的0移动到末尾，如输入 [1,,0,3,0,11,0]，输出 [1,3,11,0,0,0]
  • 只移动0，其他顺序不变
  • 必须在原数组进行操作

补充

  • 向面试官确认是否必须修改原数组
  • 数组是连续存储，要慎用，splice，unshift等API
  • 双指针思路

思路如下

  • 如果不限制必须在原数组操作
    • 定义 part1 part2 两个数组
    • 遍历数组，非 0 push 到 part1，0 push到part2
    • 返回 part1.concat(part2)
  • 有限制的情况下，遇到0push到数组末尾，用splice截取掉当前元素，此时的时间复杂度为O(n^2) 算法不可用
  • 双指针
    • 定义j指向第一个0，i指向j后面第一个非0
    • 交换i和j的值，继续向后移动
    • 只遍历一次，所以时间复杂度是O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
 * @description 移动 0 到数组末尾
 * @author sola-grj
 */

/**
 * 移动 0 到数组的末尾（嵌套循环）
 * @param arr number arr
 */

export function moveZero1(arr: number[]):void {
  const length = arr.length
  if(length === 0) return;
  
  let zeroLength = 0;
  for(let i = 0;i < length - zeroLength;i++){
    if(arr[i] === 0){
      arr.push(0)
      arr.splice(i,1) // 本身就有 O(n)
      i-- // 数组截取了一个元素，i 要递减，否则连续 0 就会有错误
      zeroLength++ // 累加 0 的长度
    }
  }
}

/**
 * 移动 0 到数组末尾（双指针）
 * @param arr number arr
 */
export function moveZero2(arr: number[]): void {
  const length = arr.length
  if(length === 0) return;
  
  let i;
  let j = -1;
  
  for (i = 0;i < length; i++){
    if(arr[i] === 0){
      if(j<0){
        j = i
      }
    }
    if(arr[i] !==0 && j >=0){
      const n = arr[i]
      arr[i] = arr[j]
      arr[j] = n
      
      j++
    }
  }
}

// 性能测试
const arr1 = []
for (let i = 0; i < 20 * 10000; i++) {
    if (i % 10 === 0) {
        arr1.push(0)
    } else {
        arr1.push(i)
    }
}
console.time('moveZero1')
moveZero1(arr1)
console.timeEnd('moveZero1') // 262ms

const arr2 = []
for (let i = 0; i < 20 * 10000; i++) {
    if (i % 10 === 0) {
        arr2.push(0)
    } else {
        arr2.push(i)
    }
}
console.time('moveZero2')
moveZero2(arr2)
console.timeEnd('moveZero2') // 3ms

单元测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @description 移动 0 到数组末尾 test
 * @author 双越老师
 */

import { moveZero1, moveZero2 } from './move-zero'

describe('移动 0 到数组末尾', () => {
    it('正常情况', () => {
        const arr = [1, 0, 3, 4, 0, 0, 0, 11, 0]
        moveZero2(arr)
        expect(arr).toEqual([1, 3, 4, 11, 0, 0, 0, 0, 0])
    })
    it('没有 0', () => {
        const arr = [1, 3, 4, 11]
        moveZero2(arr)
        expect(arr).toEqual([1, 3, 4, 11])
    })
    it('全是 0', () => {
        const arr = [0, 0, 0, 0, 0]
        moveZero2(arr)
        expect(arr).toEqual([0, 0, 0, 0, 0])
    })
})