题目描述（简单难度）

283. Move Zeroes - 图1

将所有的 0 移动到末尾，并且保持其他数字的相对顺序不变。

解法一

我的第一反应是利用两个指针，一个指针指向开头，一个指针指向末尾非零元素，然后从开头指针遍历，如果遇到 0 就和末尾指向的元素相交换，末尾指针向前移动到非零元素。

这就保证末尾指针后边元素全部是 0，当首尾指针相遇的时候结束。

但是上边的想法会使得其他数字的相对顺序改变了，我们可以逆转一下思路。不是将 0 放到末尾，而是将所有非零元素放到开头，这样就保证末尾剩下的都是 0 了。

同样利用双指针，指针 i 用于遍历数组，指针 j 开始指向开头，保证它前边的所有元素都是非 0 元素。

当 i 指针遇到非零元素就和 j 指针指向的元素交换，j 指针然后后移。

以 0,1,0,3,12 为例模拟一下过程。

  1. 0,1,0,3,12
  2. ^
  3. i
  4. j
  6. nums[i] == 0, i 后移
  7. 0,1,0,3,12
  8. ^ ^
  9. j i
  11. nums[i] != 0, 交换和 j 指向的元素, i 后移, j 后移
  12. 1,0,0,3,12
  13.   ^ ^
  14.   j i
  16. nums[i] == 0, i 后移
  17. 1,0,0,3,12
  18.   ^   ^
  19.   j   i
  21. nums[i] != 0, 交换和 j 指向的元素, i 后移, j 后移
  22. 1,3,0,0,12
  23.     ^   ^
  24.     j   i
  26. nums[i] != 0, 交换和 j 指向的元素, i 后移, j 后移, 遍历结束
  27. 1,3,12,0,0
  28.        ^   ^
  29.        j   i

可以注意到 j 前边的元素始终都是非零元素，可以结合代码再看下。

  1. public void moveZeroes(int[] nums) {
  2.     int j = 0;
  3.     for (int i = 0; i < nums.length; i++) {
  4.         //不等于 0 就交换
  5.         if (nums[i] != 0) {
  6.             int temp = nums[j];
  7.             nums[j] = nums[i];
  8.             nums[i] = temp;
  9.             j++;
  10.         }
  11.     }
  12. }

总

比较简单的一道题，双指针经常用到。用一个指针用来分割元素，使得它前边都是符合某种条件的元素。在快速排序中，也有用到这个思想。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情