当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.283.Move Zeroes

LeetCode.283.Move Zeroes


题目描述

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.

解题过程

读完题意就想到用交换,类似冒泡排序,把0逐渐都换到后面去,把非0换到前面,写了一版通过了,但非常慢,只打败了1.3%的代码:

class Solution {
    public void moveZeroes(int[] nums) {
        boolean swaped=true;//上次循环是否有过交换
        for(int i=1; i<nums.length && swaped; i++){
            swaped = false;
            for(int j=0; j<nums.length-i; j++){
                if(nums[j]==0 && nums[j+1]!=0){//交换
                    swaped=true;
                    nums[j] = nums[j] ^ nums[j+1];
                    nums[j+1] = nums[j] ^ nums[j+1];
                    nums[j] = nums[j] ^ nums[j+1];
                }
            }
        }
    }
}

基本上就是冒泡排序的套路,O(n^2)复杂度,很慢。

然后看Solution,给出了3个逐渐优化的方法:

  • 第一种方法是不用任何技巧,新申请一个等长数组,先把非零元素逐个放进去,再把后面都补上0,最后赋值给原数组。当然这个方法不符合题中原地操作(in-place)的要求。
  • 第二种方法,双指针,从前往后遍历数组,用慢指针k表示第k+1个非零元素的最终位置,由于所有非零元素肯定最终都排在数组前面,所以只要遍历到一个非零元素就可以放到nums[k]中。最后把剩下的(nums.length-k)个元素赋值为0即可。O(n)复杂度,很不错的方法了。

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

    对第二种方法,有一个优化,就是在一趟遍历过程中就将剩下的位置设为0,不需要最后再单独来一遍。里面的思想是,当右指针大于左指针时,说明右指针和左指针之间有0,这时候才需要把非零值换到前面,同时,把右指针位置设为0,省的最后再来一遍:

    public void moveZeroes(int[] nums) {
      int leftMostZeroIndex = 0; // The index of the leftmost zero
      for (int i = 0; i < nums.length; i++) {
          if (nums[i] != 0) {
              if (i > leftMostZeroIndex) { // There are zero(s) on the left side of the current non-zero number, swap!
                  nums[leftMostZeroIndex] = nums[i];
                  nums[i] = 0;
              }
    
              leftMostZeroIndex++;
          }
      }
    }
    
  • 第三种方法,还是第二种方法的优化,但比较难懂,每次遍历到非零值时,左右指针的值交换。想要弄明白为什么交换,得分开分析:
    1、left==right时,表明right左边没有0值出现,其实这时没必要交换,当然做一下交换也不会出错。
    2、left<right时,说明右指针right左边出现了0值,此时0值肯定在left位置,即nums[left]==0,所以这个left<->right交换动作其实相当于nums[left]=nums[right]; nums[right]=0;
    所以这个第三种方法和上面的第二种方法的优化是一样的,只是写法不同,写成swap让人比较难懂,而且还少了left==right时不需交换的优化。

    class Solution {
      public void moveZeroes2(int[] nums) {
          for(int left = 0,right=0; right < nums.length; right++)
              if (nums[right] != 0){
                  int temp = nums[right];
                  nums[right] = nums[left];
                  nums[left] = temp;
                  left++;
              }
      }  
    }
    

GitHub代码


上一篇 LeetCode.007.Reverse Integer

下一篇 LeetCode.541.Reverse String II

阅读
858
阅读预计4分钟
创建日期 2018-01-27
修改日期 2018-01-29
类别
百度推荐