[LeetCode]283. Move Zeroes 移动数字0

题目地址:

https://leetcode.com/problems/move-zeroes/

题目描述:

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:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

题目大意:

给你一个数组 nums ,写一个函数让所有的 0 都移到最后的同时维持其他非0数字原本的顺序。

比如说,给你 nums = [0, 1, 0, 3, 12],之后调用你的函数之后,nums 应该会是 [1, 3, 12, 0, 0].

小贴士:

  1. 你必须用这个数字本身(in-place)而不能用复制出来的副本数组。
  2. 操作次数应达到最小。

刚开始我的想法是,直接用冒泡排序法修改一下就行了。是啊多简单的事情,把冒泡排序的两层 for 循环里的那个 if 判断稍加修改,马上完成。诶等等题目有没有限定时间空间复杂度?我记得冒泡排序不是很受待见。嗯确定是没有。

是啊,简单的调试之后,系统让我过了。可是……

QQ截图20160826160933

988ms,简简单单 Accept 的开心的感觉真是一扫而空。

滥用简单算法是绝对不行的。以后面试的时候不会因为我用这样糟糕的算法 Accept 就让我进去。而且这样拉不开区分度。

所以我想到了之前上课学到的那个,用迭代遍历链表的类似方法。多写几个下标去控制,也就是多插几根旗子,到时候条件满足再进行交换,如果旗子不用就赋值为 -1 这样就不用担心了。

我定义了 i 对这个 nums 数组进行遍历操作,同时定义 j 和 k 这两根旗子帮我记录,j 记录最排头的 0 的位置,k 记录最新的非 0 数字的位置,然后两者一换就行。j 和 k 的初始值都为 -1 。不过要注意换完之后,k 旗子要拔掉,因为换完的非 0 数字没什么用了,而且交换后 nums[k] 的值是0,没有用了。然后同理, nums[j] 的值必为非 0 ,所以 j 必须做修改。一开始我想用 j = k,k = -1 这样的做法,但是这样是错误的。因为如果有两个 0 相邻的情况下,前面的 0 就被忽视了。所以直接 j = j + 1 是最正确的做法。

与此同时,为避免有两个 0 相邻的情况,我必须检查取值为 0 的数字的前一个数字是否为 0 ,如果是,那就不要动 j 旗子。

最后还遇到一个问题,就是如果数组中只有一个非 0 数字,那么 j 的初始化为 -1 ,没有值与它交换。这就很尴尬了。所以我在非 0 的条件下多进行了一条判断。

这样就稳多了。之前击败了 0.04% 的人。我击败了10000人里面的 4 个。究竟是有多少人能想到比我还慢的算法?!那我也想知道一下哈哈哈。


 

虽然想了两种办法,但是还是得查一发答案感受一下前辈的风采。

答案地址:http://www.bubuko.com/infodetail-1104600.html

“(引用)

这道题让我们将一个给定数组中所有的0都移到后面,把非零数前移,要求不能改变非零数的相对应的位置关系,而且不能拷贝额外的数组,那么只能用替换法in-place来做,需要用两个指针,一个不停的向后扫,找到非零位置,然后和前面那个指针交换位置即可,参见下面的代码:

真是令人惊叹。我的第二种解法和前辈的很像,思路基本一致。但是前辈的代码中巧妙的运用了后增运算符++,同时他的思路更加清晰,体现在于:用遍历数组的下标 i 去寻找非 0 的数字,然后用另一个下标 j 去记录 0 的位置,再进行交换,最后 j++ ,更简单,但并不容易读懂。这也是代码水平的差异。