复写零
我们先进行异地复写:代码如下
public class Test {public static void main(String[] args) {int []array ={1,0,2,3,0,4};duplicateZeros(array);}public static void duplicateZeros(int[] arr) {int [] elem=new int[arr.length];for(int cur=0,dest=0;dest<arr.length;cur++) {if(arr[cur]!=0) {elem[dest]=arr[cur];dest++;} else{elem[dest]=arr[cur];dest++;if(dest>=arr.length) {break;}//防止dest越界elem[dest]=arr[cur];dest++;}}System.out.println(Arrays.toString(elem));}
}
我们尝试在一个数组上面从左向右边复写,这样会把一个数覆盖住,从而导致连环错误。
我们现在试试从右向左复写。
我们发现从右向左的方式可以解决这个问题。
但是我们现在出现了新的问题,如何找cur位置和dest位置。
但是要注意有一种特殊情况
这种情况dest越界,我们要处理一下
我写的:
public static void duplicateZeros(int[] arr) {int cur=-1;int dest=-1;for(;dest<arr.length-1;) {cur++;if(arr[cur]==0) {dest+=2;} else {dest++;}if(dest>=arr.length) {dest--;arr[dest]=arr[cur];dest--;cur--;break;}}while(cur>=0) {if(arr[cur]==0) {arr[dest]=arr[cur];dest--;arr[dest]=arr[cur];dest--;cur--;} else{arr[dest]=arr[cur];dest--;cur--;}}}
}
官方标准写的:
class Solution{public void duplicateZeros(int[] arr){int cur = 0, dest = -1, n = arr.length;// 1. 先找到最后⼀个需要复写的数while(cur < n){if(arr[cur] == 0) dest += 2;else dest += 1;if(dest >= n - 1) break;cur++;}// 2. 处理⼀下边界情况if(dest == n){arr[n - 1] = 0;cur--; dest -= 2;}// 3. 从后向前完成复写操作while(cur >= 0){if(arr[cur] != 0) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}}