原创 2021-04-17 17:52:17

最近在leetcode上被算法题虐的体无完肤。想着建立一个算法专栏,把自己的解决问题的思路办法。与别人优秀的算法整理下。

题目
描述
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

说明
1.必须在原数组上操作,不能拷贝额外的数组。
2.尽量减少操作次数。

java代码实现
个人
一开始看到这个问题。感觉没什么难的。直接使用最暴力的解决办法。双重for循环(冒泡)的解决办法的思路。把0排到最后面。

moveZeroes(){
       int nums[] = {0,1,0,3,12,1,0,33,0};
       for(int i=0;i<nums.length;i++){
           for(int j=0;j<nums.length-1;j++){
               if(nums[j] == 0){
                   int num = nums[j+1];
                   nums[j+1] = nums[j];
                   nums[j] = num;
               }
           }
       }
       System.out.println(Arrays.toString(nums));
   }


 

虽然结果没错,但是看着个运行时间与消耗内存,就可以看出来这不是一段优秀的算法代码。使用双重for循环,大概思路就是每次把最前面的0给移动到最后。时间复杂度为O(n2-n)

评论区
这是我在评论区看到的代码

void huiwen(){
       int nums[] = {0,1,0,3,12,1,0,33,0};
       int zeronums = 0;
       int i = 0;
       for(i = 0; i < nums.length; i++) {
           if(nums[i] == 0) {
               zeronums++;
           }
           else if(zeronums != 0) {
               nums[i - zeronums] = nums[i];
               nums[i] = 0;
           }
           System.out.println(Arrays.toString(nums));
       }
   }

看到没,这就是差距,因为只执行了一次for循环,时间复杂度为O(n)。而且这个思路很有意思。

 


使用 zeronums 来存储遇到的0的个数。在排序的时候如果当前下下标的值不是0,就把当前元素的值给nums[i-zeronums],把当前元素赋值为0,而nums[i-zeronums]正好就是中间一堆0中的第一个。相当于0在中间

 

 

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在

发表评论