力扣1089 的本手妙手俗手

的本手妙手俗手

题目

本手:模拟遍历数组arr,当arr[i]为0的时候数组右移动,并且i++,避免右移之后下一个还是0又继续右移,代码如下

class Solution {
          
   
    public void duplicateZeros(int[] arr) {
          
   
        for(int i=0;i<arr.length;i++){
          
   
            if(arr[i]==0){
          
   
                rightMove(arr,i);
                i++;//避免重复右移
            }
        }
    }
    //右移
    public void rightMove(int[] arr,int x){
          
   
        for(int i=arr.length-1;i>x;i--){
          
   
            arr[i]=arr[i-1];
        }
    }
}
时间复杂度 遍历为n,右移为n,所以复杂度为O(n^2),空间复杂度为O(1)

妙手:使用双指针,设两个指针p,q为0开始遍历数组,当arr[p]=0时,q+=2,p++,否则q++,p++,当

指针p大于或者等于数组长度时遍历结束,然后通过双指针的对应回溯把数组进行修改。

class Solution {
          
   
    public void duplicateZeros(int[] arr) {
          
   
        int len=arr.length;
        int p=0,q=0;
        while(q<len){
          
   
            if(arr[p]==0){
          
   
                q+=2;
            }else{
          
   
                q++;
            }
            p++;
        }
        //因为在上个遍历中最后p++,q可能+1,可能+2,所以取最小的回退,避免值对应的值丢失
        p--;
        q--;
        while(q>=0){
          
   
          if(q<len) arr[q]=arr[p];
          if(arr[p]==0 && --q>0) arr[q]=0;
          q--;
          p--;
        }
    }
}
两次遍历每次遍历时间复杂度为n,所以时间复杂度为O(n),空间复杂度为O(1)

俗手: 将数组转为字符串,让后将字符串的“0”替换成为“00”,最后截取数组长度的字符串转为int数组

class Solution {
          
   
    public void duplicateZeros(int[] arr) {
          
   
        String str=Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining()).replaceAll("0","00");
        for(int i=0;i<arr.length;i++){
          
   
            arr[i]=str.charAt(i)-0;
        }
    }
}
时间复杂度O(n+k) n为数组长度,k为数组中字符串为0的个数,空间复杂度O(1)
经验分享 程序员 微信小程序 职场和发展