Codingbat挑战：zeroFront Stream API解决方案

Question

给定来自CodingBat的zeroFront notAlone任务：

返回一个数组，该数组包含与给定数组完全相同的数字，但重新排列以使所有零都在数组的开头分组。非零数字的顺序并不重要。因此{1,0,0,1}变为{0,0,1}。您可以修改并返回给定数组或制作一个新数组。

zeroFront([1, 0, 0, 1]) → [0, 0, 1, 1]
zeroFront([0, 1, 1, 0, 1]) → [0, 0, 1, 1, 1]
zeroFront([1, 0]) → [0, 1]

我对这个问题的解决方案在某些情况下会抛出ArrayIndexOutOfBoundsException：

public 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 i = 0; i < zeroCounter; i++) {
    zeroFront[i] = 0;
  }
  
   
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] != 0) {
      zeroFront[zeroCounter + i] = nums[i];
    }
  }
  
  return zeroFront;
}

我的问题如下：

如何解决我的问题？

如何使用Stream API解决此任务？

Answer 1

问题出在最后一个循环上。您不想将零的数量附加到当前位置，因为这显然会导致越界异常的索引。您正在遍历整个数组。您可以这样做：

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;
}

如果要使用流，可以执行以下操作：

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();
}

请记住，使用流的解决方案可能没有那么好的性能，因为有很多装箱和拆箱操作正在进行。我们还必须在集合和数组之间进行转换。

Answer 2

zeroFront的索引不正确。它不应该是零计数器i，而应该是零计数器非零计数器，其中非零计数器是迄今为止看到的非零数量。请注意，这不等于i，i是迄今为止看到的所有零和非零的总数。

要解决此问题，只需保留另一个非零计数：

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

还请注意，无需循环将zeroFront的第一个非零计数器元素设置为0。int数组的元素会自动初始化为0。

对于流解决方案，您可以利用这样一个事实，即false在true之前排序，并按x！=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;
}

没有（un）装箱，但有一些代码重复的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;
}

Answer 3

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

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

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

因为我们无法从并行执行中获得任何优势，所以实现了合并器函数来抛出断言错误。

Finisher函数将底层集合转换为数组。

该代码通过了编码BAT的所有测试：

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。流动收集器。

您的错误源于以下行：zeroFront[zeroccounter i]=nums[i] 。相反，您需要对每个新的赋值递增zeroCounter，正如埃尔文·西拉吉（ErvinSzilagyi）的回答所示。

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

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