给定一个固定长度的整数数组arr，复制每次出现零的情况，将其余元素向右移位

Question

我写了这段代码，它通过了最初的测试用例，但当我提交时，它显示了运行时错误。我不明白为什么？运行时错误：- Index -1数组超出长度8的界限

class Solution {
public int[] duplicateZeros(int[] arr) 
{
    int n=arr.length;
    int count=0;
    for(int i=0;i<n;i++)
    {
        if(arr[i]==0)
            count=count+1;
    }
    
    int loc= n-1;
    int p=n-1+count;
    if(count==0)
        return arr;
    for(int i=n-1,j=p;i>=0;i--,j--)
    {
        if(j<=n && loc>=0)
        {
            if(arr[i]==0)
            {
                arr[loc]=0;
                arr[loc-1]=0;
                loc=loc-2;
            }
            else
            {
                arr[loc]=arr[i];
                loc=loc-1;
            }
        }
    }
    return arr;

}}

Answer 1

在下面的代码中，如果loc为0，arr[i]为0，j <= n为j <= n，则输入嵌套的if和arr[loc-1]为arr[-1]，它可以提供ArrayOutOfBoundException

// If j <= n and loc is 0 enter the first if
if (j <= n && loc >= 0) {
   // If arr[i] == 0 enter the second if
   if (arr[i] == 0) {
       arr[loc] = 0;
       arr[loc - 1] = 0;   // loc is 0 so arr[loc - 1] throw the Error
       loc = loc - 2;
   } ...

Answer 2

class Solution {
    public int[] duplicateZeros(int[] arr) {
        int n = arr.length;
        int count = 0;
        /* While we are not at the end of arr and the value is 0... */
        for(; (count < n) && (arr[count] == 0); count++) {
            /* Add one to count until we are done */
        }
        
        /* If half or more of the array is 0, then we zero things and are done */
        if (count > n/2) {
            for (int i = count; i < n; i++) {
                arr[i] = 0;
            }
            return arr;
        }

        /* We have shifting work to do :'( */
        int end = n - 1;
        int loc = n - 1 - count;
        int boundary = 2 * count;
        /* Shift from loc to end while we have not copied into a space that will be 0 */
        for(; end >= boundary; end--; loc--) {
            arr[end] = arr[loc];
        }
        
        /* Put a 0 into all the spots there should be a zero, ignoreing the places there is already a 0 */
        for (int i = count; i < boundary; i++) {
            arr[i] = 0;
        }
        /* Done! */
        return arr;
    }
}

我没有测试这段代码...但它应该非常接近你想要的。我认为你的问题是你的代码过于复杂，并试图将你的步骤包装到if{} else{}逻辑中，而你不需要这样做。

您还尝试通过一次设置两个0来执行duff循环。

此外，您不需要返回arr -当您返回到caling函数时，您将修改原始数组。

Answer 3

最大的问题是您试图将结果创建到相同的数组中。如果有任何0，这是不合适的。

这是一个稍微简单一点的解决方案，需要Java 8或更高版本：

public static int[] duplicateZeros(int[] arr) {
    return Arrays.stream(arr)
        .flatMap(i -> i == 0 ? IntStream.of(i, i) : IntStream.of(i))
        .toArray();
}