README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
0283. Move Zeroes	https://leetcode.com/problems/move-zeroes/	2023-03-13 22:13:00 +0800	2023-03-13 22:13:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0283. Move Zeroes			LeetCode Go Easy Move Zeroes	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

283. Move Zeroes

題目

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Follow up: Could you minimize the total number of operations done?

題目大意

題目要求不能利用額外的輔助空間，將數字組中 0 元素都移到數字組的末尾，並與維持所有非 0 元素的相對位置。

解題思路

1. 非零交換數據, 左右指針都往右移
2. 零, 右指針右移

來源

• https://leetcode.com/problems/move-zeroes/
• https://books.halfrost.com/leetcode/ChapterFour/0200~0299/0283.Move-Zeroes/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0283.Move-Zeroes/main.go

package movezeroes

// 時間O(n^2)
func MoveZeroes(nums []int) {
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			for j := i + 1; j < len(nums); j++ {
				if nums[j] != 0 {
					nums[i], nums[j] = nums[j], nums[i]
					break
				}
			}
		}
	}
}

// 時間O(n), 空間O(1)
func MoveZeroes2point(nums []int) {
	j := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			if i != j {
				nums[i], nums[j] = nums[j], nums[i]
			}
			j++
		}
	}
}

Benchmark

goos: darwin
goarch: amd64
pkg: LeetcodeGolang/Leetcode/0283.Move-Zeroes
cpu: Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
BenchmarkMoveZeroes-4           145544966                9.164 ns/op           0 B/op          0 allocs/op
BenchmarkMoveZeroes2point-4     183269922                6.149 ns/op           0 B/op          0 allocs/op
PASS
ok      LeetcodeGolang/Leetcode/0283.Move-Zeroes        3.975s