删除值仅保留N次

Question

我今天在做Codewars的一些katas。我必须编写函数，它只保留数组中相同元素的N，例如：

{1,2,3,4,1}, N=1 -> {1,2,3,4}
{2,2,2,2}, N=2 -> {2,2}

我使用流来提出这个解决方案：

 public static int[] deleteNth(int[] elements, int maxOcurrences) {
    List<Integer> ints = Arrays.stream(elements)
                               .boxed()
                               .collect(Collectors.toList());
    return ints.stream().filter(x -> Collections.frequency(ints, x) <= maxOcurrences)
        .mapToInt(Integer::intValue)
        .toArray();
}

因此，首先将整数更改为整数，然后在频率高于N时进行过滤。但这不起作用，因为重复元素的频率相同，无论其位置如何。看起来过滤器调用后会过滤值。如何解决此问题以获得正确的值？

PS：我知道那是O（n ^ 2），但对我来说这不是问题。

Answer 1

我认为这是不使用流的一个很好的例子。当涉及有状态操作时，流并不总是最佳方法。

但它确实可以完成，而且问题也专门针对流，因此您可以使用以下内容。

---

使用forEachOrdered

您可以使用forEachOrdered来确保顺序（这里显示流必须是顺序的）：

public static int[] deleteNth(int[] elements, int maxOcurrs) {
    List<Integer> list = new ArrayList<>();
    Arrays.stream(elements).forEachOrdered(elem -> {
        if (Collections.frequency(list, elem) < maxOcurrs) list.add(elem);
    });
    return list.stream().mapToInt(Integer::intValue).toArray();
}

---

使用收集

鉴于一些环境，你可以使用collect方法来实现这一目标。

当流被排序和顺序时（Arrays.stream(elements).boxed()的情况），collect()方法不使用组合器运算符（这对于java8和java9当前的realease来说是正确的，但是不能保证在下一个版本中完全相同，因为可以发生许多优化）。

此实现保持流的顺序，并且如前所述在当前版本中正常工作。就像下面链接中的答案所说，并且在我个人看来，我发现在连续流中实现collect将需要使用组合器非常困难。

collect方法的代码如下：

public static int[] deleteNth(int[] elements, int maxOcurrs) {
    return Arrays.stream(elements).boxed()
            .collect(() -> new ArrayList<Integer>(),
                    (list, elem) -> {
                        if (Collections.frequency(list, elem) < maxOcurrs) list.add(elem);
                    },
                    (list1, list2) -> { 
                        throw new UnsupportedOperationException("Undefined combiner"); 
                    })
            .stream()
            .mapToInt(Integer::intValue)
            .toArray();
}

这个collector创建了一个ArrayList，当goind添加新元素时检查是否满足maxOcurrences，如果不满足，则添加元素。如前所述，在下面的答案中，根本没有调用组合器。这比n^2好一点。

有关为什么在序列流中不调用组合器方法的更多信息可以在here找到。

Answer 2

我发现完成手头任务的解决方案如下：

public static int[] deleteNth(int[] elements, int maxOccurrences) {
    return Arrays.stream(elements)
                 .boxed()
                 .collect(Collectors.groupingBy(Function.identity(), 
                        LinkedHashMap::new,
                        Collectors.counting()))
                 .entrySet()
                 .stream()
                 .flatMapToInt(entry ->
                    IntStream.generate(entry::getKey)
                             .limit(Math.min(maxOccurrences, entry.getValue())))
                 .toArray();
}

我们首先对元素进行分组，然后应用Collectors.counting()作为下游收集器来获取给定元素的计数。完成之后，我们只需映射给定数量的n次数，然后使用toArray急切操作收集到一个数组。

Answer 3

实际上你排除了优于maxOcurrences值的元素：

.filter(x -> Collections.frequency(ints, x) <= maxOcurrences)

我不确定完整的Stream解决方案是否是此用例的最佳选择，因为您希望根据这些值的“当前收集”数量添加一些值。

在这里我将如何实现：

public class DeleteN {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(deleteNth(new int[] { 1, 2, 3, 4, 1 }, 1)));
        System.out.println(Arrays.toString(deleteNth(new int[] { 2, 2, 2, 2 }, 2)));
    }

    public static int[] deleteNth(int[] elements, int maxOcurrences) {

        Map<Integer, Long> actualOccurencesByNumber = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        Arrays.stream(elements)
              .forEach(i -> {
                  Long actualValue = actualOccurencesByNumber.computeIfAbsent(i, k -> Long.valueOf(0L));
                  if (actualValue < maxOcurrences) {
                      result.add(i);
                      actualOccurencesByNumber.computeIfPresent(i, (k, v) -> v + 1L);
                  }
              });

        return result.stream().mapToInt(i -> i).toArray();
    }
}

输出：

[1, 2, 3, 4]

[2, 2]