leetcode - [283] Move Zeroes

2020/02/14

题目描述

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.

给一个数组,将其中为零的值全部移到末尾,并保持非零数值的顺序。

举个例子:

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

解法1

自己的思路:

首先,遍历一遍数组,从头依次赋非零数值,并记录非零数值的最后一位下一位的索引idx

然后,遍历第二次数组,从idx至数组尾部全部赋0

@Test
public void question283(){
    int[] input  = {0, 1, 0, 3, 12};
    int   length = input.length;
    int[] output = new int[length];

    int idx = 0;
    for (int i : input) {
        if (i != 0) {
            output[idx++] = i;
        }
    }
    while (idx < length){
        output[idx++] = 0;
    }
}

解法2

看了下别人的解法,发现了一种更高效的方式:仅遍历一次

具体,如下图所示:

public class Utils {
    public static void swap(int[] a, int i, int j){
        int t = a[i];
        a[i]  = a[j];
        a[j]  = t;
    }
}

@Test
public void improve283(){
    int[] nums = {0, 1, 0, 3, 12};
    int zeroIdx = 0;

    for (int i = 0; i < nums.length; i++){
        if (nums[i] != 0){
            Utils.swap(nums, i, zeroIdx++);
        }
    }
    System.out.println(Arrays.toString(nums));
}

Update 2020_0526

此题的关键在于先按循序排列非零元素,剩余的元素自然而然全部都是零。

所以我们使用两个指针完成这件事情:

首先,使用start变量,其初始值为0

然后,依次遍历nums原始数组,一旦发现非零元素,直接与nums[start]元素互换,最后start加一。

class Solution {
    public void moveZeroes(int[] nums) {
        int start = 0, len = nums.length;
        for (int i = 0; i < len; i++){
            if (nums[i] != 0){
                swap(nums, i, start++);
            }
        }
    }
    private void swap(int[] nums, int i, int j){
        int t   = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
    
}

Enjoy it!


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory