Codingbat 挑战：zeroFront Stream API 解决方案

问题出在最后一个循环上。您不希望将零的数量附加到当前位置，因为这显然会导致索引出界异常。您正在遍历整个数组。您可以做的是按以下方式递增：zeroCounter

public static int[] zeroFront(int[] nums) {
    if (nums.length == 0) {
        return nums;
    }

    int[] zeroFront = new int[nums.length];
    int zeroCounter = 0;

    for (int i = 0; i < zeroFront.length; i++) {
        if (nums[i] == 0) {
            zeroCounter++;
        }
    }

    for (int num : nums) {
        if (num != 0) {
            zeroFront[zeroCounter++] = num;
        }
    }

    return zeroFront;
}

如果你想使用 ，你可以做这样的事情：streams

public int[] zeroFront(int[] nums) {
    Map<Boolean, List<Integer>> partitions = Arrays.stream(nums).boxed().collect(Collectors.partitioningBy(i -> i == 0));
    List<Integer> result = new ArrayList<>(partitions.get(true));
    result.addAll(partitions.get(false));
    return result.stream().mapToInt(i -> i).toArray();
}

正如 @Alexander Ivanchenko 在评论中指出的那样，这可以进一步优化以摆脱中间列表：result

public static int[] zeroFrontStream(int[] nums) {
    Map<Boolean, List<Integer>> partitions = Arrays.stream(nums).boxed().collect(Collectors.partitioningBy(i -> i == 0));
    return Stream.concat(partitions.get(true).stream(), partitions.get(false).stream()).mapToInt(i -> i).toArray();
}

请记住，具有流的解决方案可能性能不高，因为有很多装箱和拆箱正在进行。我们还必须在集合和数组之间进行转换。

的索引不正确。它不应该是 ，而是 ，到目前为止看到的非零的数量在哪里。请注意，这不等于 ，这是迄今为止看到的所有零和非零的总数。zeroFrontzeroCounter + izeroCounter + nonZeroCounternonZeroCounteri

要修复它，只需再计算一次非零：

int nonZeroCount = 0;
for (int num : nums) {
    if (num != 0) {
        zeroFront[zeroCounter + nonZeroCount++] = num;
    }
}

另请注意，不需要将第一个元素设置为 0 的循环。int 数组的元素会自动初始化为 0。nonZeroCounterzeroFront

对于流解决方案，您可以利用之前排序的事实，并按以下顺序对数组进行排序：falsetruex != 0

public static int[] zeroFrontStreams(int[] nums) {
    return Arrays.stream(nums).boxed().sorted(Comparator.comparing(x -> x != 0)).mapToInt(x -> x).toArray();
}

但请注意，由于这涉及排序，因此与 O（n） 解决方案相比，其时间复杂度更差。还涉及很多装箱/拆箱。

或者，如果您只想在代码中的某个位置使用流，则可以使用它来将数组分成零和非零，然后以其他方式将非零复制到尾部：zeroFront

public static int[] zeroFrontStreams(int[] nums) {
    var partitions = Arrays.stream(nums).boxed().collect(Collectors.partitioningBy(x -> x == 0));
    int[] zeroFront = new int[nums.length];
    int[] nonZeros = partitions.get(false).stream().mapToInt(x -> x).toArray();
    int zeroCounter = partitions.get(true).size();
    System.arraycopy(nonZeros, 0, zeroFront, zeroCounter, nonZeros.length);
    return zeroFront;
}

没有（取消）装箱，但有一些代码重复：Arrays.stream(nums).filter

public static int[] zeroFront(int[] nums) {
    int[] zeroFront = new int[nums.length];
    long zeroCounter = Arrays.stream(nums).filter(x -> x == 0).count();
    int[] nonZeros = Arrays.stream(nums).filter(x -> x != 0).toArray();
    System.arraycopy(nonZeros, 0, zeroFront, (int)zeroCounter, nonZeros.length);
    return zeroFront;
}

可以在单个流语句中使用 Stream IPA 完成此任务，而无需使用自定义收集器进行排序。

要创建收集器，我们可以使用静态方法 Collector.of（）。我们需要提供收集器内部使用的可变容器，并指定如何将流的元素添加到容器中，以及如何在并行执行的情况下合并两个容器。

在下面的代码中，用作可变容器。它是一个数组支持的集合，允许在后面和前面插入一个恒定时间 O（1） 的新元素。ArrayDeque

由于我们无法从并行执行中获得任何优势，因此实现了 combiner 函数来抛出 .AssertionError

Finisher 函数将基础集合转换为数组。

此代码通过了 CodingBat 上的所有测试：

public int[] zeroFront(int[] nums) {
    return Arrays.stream(nums)
        .boxed()
        .collect(Collector.of(
            ArrayDeque::new,
            (Deque<Integer> deque, Integer next) -> {
                if (next == 0) deque.addFirst(next);
                else deque.addLast(next);
            },
            (left, right) -> { throw new AssertionError("should not be processed in parallel"); },
            deque -> deque.stream().mapToInt(Integer::intValue).toArray()
        ));
}

要在 CodingBat 上运行此代码，您需要使用完全限定名称 java.util.stream.Collector。

你的错误根植于这条线.相反，您需要随着每个新任务的增加而增加，正如 Ervin Szilagyi 的回答中已经显示的那样。zeroFront[zeroCounter + i] = nums[i];zeroCounter

此外，下面的循环是多余的，因为当为数组分配内存时，其所有元素都将使用默认值 ：forint[]0

for (int i = 0; i < zeroCounter; i++) {
    zeroFront[i] = 0;
}

正如其他人已经指出了您的错误，这里有另一种使用带有 teeing 收集器的流来解决此问题的方法（这是在 java 12 中添加的，不确定正在运行哪个版本的 java codingbat）：

public int[] zeroFront(int[] nums) {
    return Arrays.stream(nums).boxed().collect(
            Collectors.teeing(
                    Collectors.filtering(n -> n == 0, Collectors.toList()),
                    Collectors.filtering(n -> n != 0, Collectors.toList()),
                    (zeros, nonZeros) -> Stream.concat(zeros.stream(), nonZeros.stream())
                            .mapToInt(Integer::intValue)
                            .toArray()
            ));
}