GuilinDev

Lc0283

05 August 2008

283 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.

Example:

1
2

Input: [0,1,0,3,12]
Output: [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.

题意和分析

给一个数组，把其中的0挪到最后面去，非0元素的相对顺序不能变，不能另外开一个数组；使用两个指针，从0位置开始查，找到不为0的元素后，与另外一个指针交换值，直到末尾。

代码

同向双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int len = nums.length;
        int slow = 0;
        int fast = 0;
        
        while (fast < len) {
            // switch
            if (nums[fast] != 0) {//把不为0的元素一次挪到头部去
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
            fast++;
        } 
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public void moveZeroes(int[] nums) {
        int zeroIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (i != zeroIndex) { // 优化下，相同元素不用交换
                    nums[i] = nums[i] ^ nums[zeroIndex];
                    nums[zeroIndex] = nums[i] ^ nums[zeroIndex];
                    nums[i] = nums[i] ^ nums[zeroIndex];
                }
                zeroIndex++;
            } 
        }
    }
}
This site is open source. Improve this page.