力扣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)