[数据结构与算法]算法练习-LeetCode Hot 100 283. 移动零

今日心情：那就继续下去吧！

题目描述：

LeetCode Hot 100 283. 移动零

?给定一个数组?nums，编写一个函数将所有?0?移动到数组的末尾，同时保持非零元素的相对顺序。请注意?，必须在不复制数组的情况下原地对数组进行操作。

?

解题代码1：（自己想的用栈：非0元素先进栈，然后弹出，最后栈为空的时候补0）

class Solution {
    public void moveZeroes(int[] nums) {
        LinkedList<Integer> stack = new LinkedList<>();

        for(int i = nums.length-1; i >=0;i--){
            if(nums[i]!=0) stack.addLast(nums[i]);
        }

        for(int i = 0; i< nums.length ;i++){
            if(!stack.isEmpty()){
                nums[i] = stack.getLast();
                stack.removeLast();
            }else{
                nums[i] = 0;
            }
        }

    }
}

解题代码2：（双指针）

class Solution {

    //解法2: 双指针
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = 0;

        while(right < len){
            if(nums[right] != 0){
              swap(nums,left,right);
              left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

解题思路：

自己一开始拿到题直接想到的是采用栈，对于非0数直接依次入栈，然后出栈重新赋值给数组，当所有元素出栈，栈为空，此时对于剩下的数组的元素值修改为0。栈的实现使用的是LinkedList当然也可以用Stack实现，注意的是将元素压入栈中的操作不同，弹出的操作也不同。最终Stack实现比用LinkedList实现所花的时间要长。

采用双指针的方法然后进行交换原地修改：

（1）循环条件right指针小于数组长度len，当right指针超过len，则停止循环；

（2）right 和 left 指针同时开始， right 指针用于指向非0元素值，将left 和 right 元素交换实现将非0元素交换到0元素的左边，即将0元素一直移动到数组尾部。

???????