java - 非法状态异常 : "Duplicate key" for Collectors. toMap()

Question

Reference Question: Numbers which constitute the Maximum sum

我正在编写一个程序，该程序将打印构成最大总和的元素。我已经能够通过任何随机场景，但是当我的最大总和由两组组成时，我的代码会失败。

我的代码:

class Ideone {
    public static void main(String[] args) throws java.lang.Exception {
        Scanner reader = new Scanner(System.in);
        int TestCases = reader.nextInt();
        reader.nextLine();
        String[] output = new String[TestCases];
        String sss = "";
        String ddd = "";

        for (int k = 0; k < TestCases; k++) {
            int noofELements = reader.nextInt();
            reader.nextLine();
            String[] al = reader.nextLine().split(" ");
            List<Integer> numbers = Arrays.stream(al).map(Integer::valueOf).collect(Collectors.toList());
            Ideone mm = new Ideone();
            String maxi = mm.maximumm(numbers, ddd);
            sss = sss.concat(maxi);

        }
        System.out.println(sss);

    }

    public String maximumm(List<Integer> numbers, String sss) {
        int toIndex = 3, fromIndex = 0;
        List<Integer> result = new ArrayList<>();
        while (toIndex < numbers.size()) {
            Map<Integer, Integer> map =
                IntStream.range(fromIndex, toIndex).mapToObj(i -> new AbstractMap.SimpleEntry<>(i, numbers.get(i)))
                    .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));
            // find max of sublist
            int maxOfSub = numbers.subList(fromIndex, toIndex).stream().max(Integer::compareTo).get();
            //update indexes
            fromIndex = map.get(maxOfSub) + 2;
            toIndex += fromIndex;

            result.add(maxOfSub);
        }
        int lastMax = numbers.subList(fromIndex, numbers.size()).stream().max(Integer::compareTo).get();
        if (lastMax > 0) {
            result.add(lastMax);
        }
        result = result.stream().sorted(Integer::compareTo).collect(Collectors.toList());
        //System.out.println(result);
        sss = sss.concat(result.toString().replace(", ", "").replace("]", "").replace("[", ""));
        return sss;
        //  return result.stream().reduce(0,Integer::sum);
    }
}

例如，当我输入 4 5 4 3 时，非相邻元素的最大总和为 8 ，这将由 4 4 或 5 3。

我的完整代码工作正常，只是我无法在最终结果中获得这两个结果。

我的错误日志:

Exception in thread "main" java.lang.IllegalStateException: Duplicate key 0 at java.util.stream.Collectors.lambda$throwingMerger$0(Collectors.java:133) at java.util.HashMap.merge(HashMap.java:1254) at java.util.stream.Collectors.lambda$toMap$58(Collectors.java:1320) at java.util.stream.ReduceOps$3ReducingSink.accept(ReduceOps.java:169) at java.util.stream.IntPipeline$4$1.accept(IntPipeline.java:250) at java.util.stream.Streams$RangeIntSpliterator.forEachRemaining(Streams.java:110) at java.util.Spliterator$OfInt.forEachRemaining(Spliterator.java:693) at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:481) at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471) at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708) at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:499) at Ideone.maximumm(Ideone.java:47) at Ideone.main(Ideone.java:27)

错误指向这一行:result.add(maxOfSub);

任何帮助都会很好:)

Answer 1

此错误的原因是您有重复的 <key>当您调用Stream.collect()时。请记住，此方法对流元素执行可变归约操作。所以当你打电话时:

.collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey));

在这里，您定义 <keys>的Map对象为<values>的Entry<index, values>由 Stream.mapToObj() 定义方法。现在，在数据测试中，您有 4, 5, 4, 3 ，这意味着，您正在尝试创建 <key>号码 4两次。因此，你得到了这个IllegalStateException .

但是我该如何解决这个问题？

很简单，只要切换你的Map的定义即可来自 <values, indexes> 的对象至<indexes, values>在 Stream.collect()称呼。 我该如何做到这一点？好吧，只需替换 Map.Entry::getValue与 Map.Entry::getKey反之亦然，如下所示:

.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

此外，使用 IntStream.boxed() 有更好的等价物方法。此方法返回 Stream由该流的元素组成，每个元素装箱为 Integer 。对我来说，这是转换 List 的最佳方式对象变成 Map像这样的对象:

Map<Integer, Integer> map = IntStream
        .range(fromIndex, toIndex)
        .boxed()
        .collect(Collectors.toMap(i -> i, i -> numbers.get(i) > 0 ? numbers.get(i) : 0));

请注意，我正在使用此表达式 i -> numbers.get(i) > 0 ? numbers.get(i) : 0分配 <values> Map的目的。 为什么要这样做？因为，我们需要跟踪删除负数，所以我用零替换它们。 Stream.filter()方法是一种替代方法，但是 Map对象将不包含过滤后的元素。

但是，此修改将影响您更新索引的方式，因为现在映射值是 <values>而不是<indexes>如这一行所示:

fromIndex = map.getOrDefault(maxOfSub, toIndex - 1) + 2;

要解决此问题，您只需转换获取 <index>来自通讯员<value>像这样:

fromIndex = IntStream
        .range(fromIndex, toIndex)
        .filter(i -> map.get(i).equals(maxOfSub))
        .findFirst()
        .orElse(toIndex - 1) + 2;

替代解决方案

现在，以上信息只能解决IllegalStateException 。然而，我发现还有另一个错误。如果我使用这个数字数组 1, 9, 1, 7, 7, 5, 4, 1, 6 ，非相邻数字的最大和应为 [9 + 7 + 5 + 6] = 27但你的代码得到 [9 + 7 + 6] = 22 。所以我试图在这里找到解决方案:

public class Ideone
{
    public static void main(String[] args)
    {
//        List<Integer> numbers = Arrays.asList(4, 5, 4, 3);
//        List<Integer> numbers = Arrays.asList(1, 9, 1, 7, 7, 5, 4, 1, 6);
        List<Integer> numbers = Arrays.asList(-1, 7, 8, -5, 4, 9, -2, 3);

        String sss = "";
        String ddd = "";
        Ideone mm = new Ideone();

        List<List<Integer>> maxi = mm.findMaxSumNonAdjacentStream(numbers, numbers.size());
        System.out.println(Collections.singletonList(maxi));

    }

    public List<List<Integer>> findMaxSumNonAdjacentStream(List<Integer> numbers, int size)
    {
        int fromIndex = 0;

        Map<Integer, Integer> maxSumMap = IntStream
                .range(fromIndex, size)
                .boxed()
                .collect(Collectors.toMap(i -> i, i -> numbers.get(i) > 0 ? numbers.get(i) : 0));

        Map<Integer, List<Integer>> indexMap = IntStream
                .range(fromIndex, size)
                .mapToObj(i -> new AbstractMap.SimpleEntry<>(i, Collections.singletonList(numbers.get(i))))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

        maxSumMap.replace(1, Math.max(numbers.get(1), numbers.get(0)));

        List<Integer> maxValList = maxSumMap
                .entrySet()
                .stream()
                .filter(entry -> entry.getKey() > 1)
                .map(entry -> {
                    int index = entry.getKey();
                    int prevOne = index - 1;
                    int prevTwo = index - 2;
                    int prevValOne = maxSumMap.getOrDefault(prevOne, 0);
                    int prevValTwo = maxSumMap.getOrDefault(prevTwo, 0);

                    int maxVal = Math.max(prevValOne, prevValTwo + entry.getValue());
                    boolean exclude = prevValOne > (prevValTwo + entry.getValue());

                    List<Integer> elements = new ArrayList<>();
                    if (prevValOne > 0 && exclude) {
                        elements = new ArrayList<>(indexMap.get(prevOne));
                    } else if (prevValTwo > 0 && !exclude) {
                        elements = new ArrayList<>(indexMap.get(prevTwo));
                    }

                    if (!exclude) {
                        elements.add(entry.getValue());
                        elements = elements.stream().sorted(Integer::compareTo).collect(Collectors.toList());
                    }

                    maxSumMap.replace(index, maxVal);
                    indexMap.replace(index, elements);

                    return index;
                })
                .collect(Collectors.toList());

        Integer max = maxValList
                .stream()
                .mapToInt(v -> v)
                .max().orElseThrow(NoSuchElementException::new);

        int lastMax = maxValList.stream().max(Integer::compareTo).orElse(-1);
        Integer maxVal = maxSumMap.get(max);

        List<Integer> result = maxSumMap
                .entrySet()
                .stream()
                .filter(entry -> entry.getValue().equals(maxVal))
                .map(i -> i.getKey())
                .collect(Collectors.toList());

        Predicate<Map.Entry<Integer, List<Integer>>> containMaxList =
                mapEntry -> result.contains(mapEntry.getKey());

        return indexMap.entrySet()
                .stream()
                .filter(containMaxList)
                .map(i -> i.getValue())
                .collect(Collectors.toList());
    }
}