LeetCode283. Move Zeroes 解答

绝地灬酷狼 2022-06-07 08:50 156阅读 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:  
> You must do this in-place without making a copy of the array.  
> Minimize the total number of operations.  
> 题目大意：给定一个名为nums的数组，你要写一个函数来将这个数组里面所有的0移动到数组的末尾，其他元素的顺序保持不变。特别要求：不能够使用额外的空间，尽量减少操作步数

\#解答过程  
我的办法是从后面往前遍历数组，如果碰到了0，则将后面的所有元素往前移动一个位，最后在末尾把0加上。写成代码是这样子：

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

虽然直觉告诉我时间复杂度为O(n\*n)的程序就算是accept了也不会有什么好下场，一定会有一种算法只需要遍历一遍的，但是我还是没想到我的算法竟然排到了后10%… 来看看更好的算法  
\#更好的算法

class Solution {
        public void moveZeroes(int[] nums) {
            int cnt = 0;
            for (int i=0;i<nums.length;i++) {
                if (nums[i]==0) cnt++;
                else nums[i-cnt]=nums[i];
            }
            
            for (int len=nums.length-1;cnt>0;cnt--) {
                nums[len--]=0;
            }
        }
    }

这个是目前效率最高的算法，他做到了一边遍历一边操作，虽然遍历了两遍，但是时间复杂度仍然为O(n)，并且也非常简洁。