[LeetCode]Move Zeroes-白红宇

[LeetCode]Move Zeroes

阅读量：5010 次

发布时间：2019-06-12

本文共 3130 字，大约阅读时间需要 10 分钟。

题目描述：

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

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.

Minimize the total number of operations.

题目大意：

给定一个数组nums，编写函数将数组内所有0元素移至数组末尾，并保持非0元素相对顺序不变。

例如，给定nums = [0, 1, 0, 3, 12]，调用函数完毕后， nums应该是 [1, 3, 12, 0, 0]。

注意：

你应该“就地”完成此操作，不要复制数组。

最小化操作总数。

解题思路：

题目可以在O(n)时间复杂度内求解

算法步骤：

使用两个"指针"x和y，初始令y = 0

利用x遍历数组nums：

若nums[x]非0，则交换nums[x]与nums[y]，并令y+1

算法简析：

y指针指向首个0元素可能存在的位置

遍历过程中，算法确保[y, x)范围内的元素均为0

package mainimport "fmt"func main() {	slice := []int{0, 1, 0, 3, 12, 0, 0, 1, 2, 3, 0, 0, 1, 0, 1, 0, 8, 9, 0, 0, 0}	fmt.Println("最终的数组：", move(slice))}func move(a []int) []int {	var y int = 0	var x int	for x = 0; x < len(a); x++ {		if a[x] != 0 {			a[x], a[y] = a[y], a[x]			y++		}	}	return a}

本文来源：http://bookshadow.com/weblog/2015/09/19/leetcode-move-zeroes/

------------------------------------历史分割线------------------------------------

之前的思路：

package mainimport "fmt"func main(){	slice := []int{0,1,0,3,12,0,0,1,2,3,0,0,1,0,1,0,8,9,0,0,0}		fmt.Println("最终的数组：",move(slice))}func move(a []int) []int{	var l int = len(a)    temp := 0    count := 0	for i:= 0;i < l;i++{		if a[i] == 0{			fmt.Println("换位置之前的数组：",a)						count++			temp = a[i]			for j := i ;j < (l-1);j++{				a[j] = a[j + 1]			}			a[l-1] = temp						fmt.Println("换位置之后的数组：",a)			fmt.Println("----------------")		}				if count + i < l {			if a[i] == 0 {			   i--		    }		}else {			return a		}	}    return a}

输出结果：

换位置之前的数组： [0 1 0 3 12 0 0 1 2 3 0 0 1 0 1 0 8 9 0 0 0]

换位置之后的数组： [1 0 3 12 0 0 1 2 3 0 0 1 0 1 0 8 9 0 0 0 0]

----------------

换位置之前的数组： [1 0 3 12 0 0 1 2 3 0 0 1 0 1 0 8 9 0 0 0 0]

换位置之后的数组： [1 3 12 0 0 1 2 3 0 0 1 0 1 0 8 9 0 0 0 0 0]

----------------

换位置之前的数组： [1 3 12 0 0 1 2 3 0 0 1 0 1 0 8 9 0 0 0 0 0]

换位置之后的数组： [1 3 12 0 1 2 3 0 0 1 0 1 0 8 9 0 0 0 0 0 0]

----------------

换位置之前的数组： [1 3 12 0 1 2 3 0 0 1 0 1 0 8 9 0 0 0 0 0 0]

换位置之后的数组： [1 3 12 1 2 3 0 0 1 0 1 0 8 9 0 0 0 0 0 0 0]