【数据结构与算法】(13):移动0到数组末尾


字数:743 阅读时长:4分钟 阅读:85

经典算法题:给出一个数组,要求把数组中所有的 0 移动到数组末尾,要求在原数组上进行操作。

数据结构与算法 · 移动0到数组末尾

一、问题示例

示例 1:

  • 输入:[1,2,0,5,0,7]
  • 输出:[1,2,5,7,0,0]

示例 2:

  • 输入:[1,0,2,0,0,0,5,7]
  • 输出:[1,2,5,7,0,0,0,0]

二、代码演示

  1. for + splice 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 移动 0 到数组末尾 for splice

export function moveZero1(arr:number[]):void {
const len = arr.length;
if (len === 0) return
let zeroLen = 0
for (let i = 0; i < len - zeroLen; i++) {
if (arr[i] === 0) {
arr.push(0)
arr.splice(i, 1) // splice O(n)
i--
zeroLen++ // 增加 0 的长度
}
}
}
  1. for + 双指针 实现
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
// 移动 0 到数组末尾 for slice

export function moveZero2(arr:number[]):void {
const len = arr.length
if (len === 0) return
let i = 0
let j = -1

for (;i < len;i++) {
if (arr[i] === 0) {
// 第一个 0
if (j<0) {
j = i
}
}

if (arr[i] !== 0 && j >= 0) {
// 交换
const n = arr[i]
arr[i] = arr[j]
arr[j] = n

j ++
}
}
}

三、单元测试

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
import { moveZero1, moveZero2 } from '../move-zero.ts'

describe('移动 0 到数组末尾', () => {
it('正常情况', () => {
let arr = [0,2,5,0,2,0,0,2,50,0,3]
moveZero1(arr)
expect(arr).toEqual([2, 5, 2, 2, 50, 3, 0, 0, 0, 0, 0])
})
it('没有 0', () => {
let arr = [1,2,3,4,6,7]
moveZero1(arr)
expect(arr).toEqual([1,2,3,4,6,7])
})
it('全是 0', () => {
let arr = [0,0,0,0,0]
moveZero1(arr)
expect(arr).toEqual([0,0,0,0,0])
})
})

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

四、性能测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const arr5 = []
for (let i = 0; i < 20 * 10000; i++) {
if (i % 2 === 0) {
arr5.push(0)
} else {
arr5.push(i)
}
}
let arr6 = JSON.parse(JSON.stringify(arr5))

console.time('moveZero1')
moveZero1(arr5)
console.timeEnd('moveZero1')

console.time('moveZero2')
moveZero2(arr6)
console.timeEnd('moveZero2')





moveZero1 run time: 0


moveZero2 run time: 0


五、算法复杂度

方法时间复杂度
for + spliceO(n^2)
for 双指针O(n)

欢迎访问:天问博客

本文作者: Tiven
发布时间: 2023-07-21
最后更新: 2023-07-24
本文标题: 【数据结构与算法】(13):移动0到数组末尾
本文链接: https://www.tiven.cn/p/68ab9db6/
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处!
欢迎留言,提问 ^_^
个人邮箱: tw.email@qq.com
notification icon
博客有更新,将会发送通知给您!