283. Move Zeroes

爱被打了一巴掌 2022-06-12 06:15 153阅读 0赞

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元素，将找到的0元素所在的位置之后的第一个非零元素所在位置的值与当前0元素所在位置的0值交换，即可保持非零元素的值的相对位置不变，循环结束后所有0都会被移到数组末尾。

解决本问题使用两层循环：外层循环遍历数组，找0元素所在的位置；内层循环找当前0元素所在位置之后的第一个非零元素。当当前位置的值为0时执行内层循环，假设当前位置i的值num\[i\]=0，内层循环的j = i++，即从当前0元素所在的下一个位置开始查找非零元素；当nums\[j\] != 0时，nums\[i\] = nums\[j\]，nums\[j\]=0，即交换nums\[i\]、nums\[j\]的值，并退出内层循环，执行外层循环。

public class Solution {
        public void moveZeroes(int[] nums) {  
            for(int i = 0;i<nums.length;i++){
                if(nums[i] == 0){
                    for(int j = i+1;j<nums.length;j++){
                        if(nums[j] != 0){
                            nums[i] = nums[j];
                            nums[j] = 0;
                            break;
                        }
                    }
                }
            }
        }
    }