避免在Java 8 stream reduce方法中使用全局变量

Question

我试图使用Java 8重写Moore的投票算法的实现,以找到数组中的多数元素.

Java 7实现将是这样的:

public int findCandidate(int[] nums) {

    int maj_index = 0, count = 1;
    for(int i=1; i<nums.length;i++){
        if(count==0){
            count++;
            maj_index=i;
        }else if(nums[maj_index]==nums[i]){
            count++;
        } else {
            count--;
        }
    }
    return nums[maj_index];
}

我能想到的方法是使用stream reduce来获得最终结果

public int findCandidate(int[] nums) {
    int count = 1;
    Arrays
            .asList(nums)
            .stream()
            .reduce(0, (result, cur) -> {
                if (count == 0) {
                    result = cur;
                    count++;
                } else if (result == cur){
                    count++;
                } else {
                    count --;
                }
            });
    return result;
}

但是这个方法有编译错误,而且它也打破了函数纯粹主义者,我多次遇到这种情况,那么处理lambda表达式中的全局变量的最佳方法是什么.

Answer 1

Yassin Hajaj的答案显示了一些非常好的流技术.(+1)从根本上说,我认为它采用了正确的方法.不过,可以对它进行一些小的改进.

第一个更改是使用counting()收集器来计算每个组中的项目,而不是将它们累积到列表中.由于我们正在寻找多数,我们所需要的只是计数,而不是实际的元素,我们避免必须比较列表的长度.

第二个更改是过滤列表,查找计数占多数的组.根据定义,最多只能有一个,所以我们只使用这个谓词过滤映射条目,findAny而不是使用终止流max.

第三个变化是使函数返回OptionalInt更接近其意图.该OptionalInt要么包含了大部分价值,或者如果没有多数值是空的.这避免了必须使用诸如-1可能实际发生在数据中的标记值.由于findAny回报的OptionalInt,我们就大功告成了.

最后,我在几个地方依赖静态导入.这主要是风格问题,但我认为它会稍微清理一下代码.

这是我的变化:

static OptionalInt majority(int... nums) {
    Map<Integer, Long> map =
        Arrays.stream(nums)
              .boxed()
              .collect(groupingBy(x -> x, counting()));

    return map.entrySet().stream()
              .filter(e -> e.getValue() > nums.length / 2)
              .mapToInt(Entry::getKey)
              .findAny();
}

Answer 2

因此，就像我在评论中告诉您的那样，在 lambda 表达式中使用可变对象是不行的。但就你而言，如果你真的想应用相同的算法，那就很困难了。

这是一个会做与你想要的相同的事情，如果没有找到多数，它会返回-1

public static int findCandidate(int ... nums) {
    Map<Integer, List<Integer>> map =
    Arrays.stream(nums)
          .boxed()
          .collect(Collectors.groupingBy(x -> x));
    int value = 
          map
          .entrySet().stream()
          .max((e1, e2) -> Integer.compare(e1.getValue().size(), e2.getValue().size()))
          .map(e -> e.getKey())
          .get();
    int result = map.get(value).size();
    return result > nums.length / 2 ? value : -1;
}