java - 如何处理大数组/列表

Question

最近我尝试做一些 codility 任务。 我经常使用数组作为输入来执行任务，您需要解决这样的问题:找到数组中未出现的最小正整数等。 我可以轻松处理小数组，但是当我提交代码并通过测试获取摘要(包括具有 >1000(或 10 000)元素的数组时，我几乎总是会遇到运行时错误。

那么你能告诉我如何处理大数组吗？

大多数情况下，我尝试将数组转换为列表，如下所示:

List<Integer> arrayList = Arrays.stream(A)
                .boxed()
                .filter(c -> (c > -1001 && c < 1001)) // predicate
                .collect(Collectors.toList());

有时我会使用过滤器，就像你看到的，有时我会根据需要使用不同/排序。 但我仍然有很多运行时错误。

如果我能提供一些如何处理它的提示，我将不胜感激。

@cricket_007

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] A) {

        List<Integer> integerList = Arrays.stream(A)
                .boxed()
                .collect(Collectors.toList());

        if ((integerList.size() == 2 && integerList.get(0) == integerList.get(1)) || A.length == 1) {
            return 0;
        }
        if ((integerList.size() == 2 && integerList.get(0) != integerList.get(1))) {
            return Math.abs(integerList.get(0) - integerList.get(1));
        }

        int sublistSum1;
        int sublistSum2;

        List<Integer> scoreList = new ArrayList<>();

        Integer temp;
        for (int i = 1; i < integerList.size(); i++) {
            sublistSum1 = integerList.subList(0, i).stream().mapToInt(n -> n).sum();
            sublistSum2 = integerList.subList(i, integerList.size()).stream().mapToInt(n -> n).sum();
            temp = Math.abs(sublistSum1 - sublistSum2);
            scoreList.add(temp);
        }
        return scoreList.stream()
                .min(Integer::compareTo)
                .get();
    }
}

这是我对这个任务的解决方案:https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

我得到了 100% 的正确性，但性能为 0%，因为:“超时错误已终止。已达到硬限制:6.000 秒。”所有 6 次性能测试都返回此错误。

这种情况我能做什么？

下一个任务，下一个大数组问题。 https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

我的代码:

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {

        if (Arrays.stream(A).distinct().count() == 1) {
            return 0;
        }
        int score = 0;

        for (int i = 0; i < A.length; i++) {
            if (A[i] == 0) {
                for (int j = 1; j < A.length; j++) {
                    if (A[j] == 1 && j > i) {
                        score++;
                    }
                }
            }
        }
        if (score < 1_000_001) {
            return score;
        }
        return -1;
    }
}

所以基本上，当我尝试使用嵌套循环解决此任务时，我得到了 O(N^2) 算法复杂度。怎么解决？

Answer 1

首先，你要问自己是否真的需要List<Integer>这需要拳击或者如果 int[]数组也足以完成您的任务。

所以

int[] array = Arrays.stream(A)
    .filter(c -> (c > -1001 && c < 1001))
    .toArray();

将会更加高效。但如果您确实需要 List<Integer> ，在对值进行装箱之前，您仍然应该做尽可能多的工作，即

List<Integer> arrayList = Arrays.stream(A)
    .filter(c -> (c > -1001 && c < 1001))
    .boxed()
    .collect(Collectors.toList());

这样，只有匹配的int值被装箱而不是全部。这是 Stream 实现本身无法执行的优化，就像您使用 .boxed().filter(c -> (c > -1001 && c < 1001)) 时一样。您正在调用filter在Stream<Integer>上，通过Predicate<Integer>而不是IntPredicate并且实现别无选择，只能传递 Integer到该代码。

类似的情况适用于sort ;当应用于原始类型数据时，它比 Integer 更有效对象。 distinct 也有类似的潜力。 ，但据我所知，这在当前的实现中并未实现。

那么你必须自己实现更好的算法，这就是挑战所在。

查找数组中未包含的最小正整数的一种解决方案是

int first = Arrays.stream(A)
    .filter(i -> i >= 0)
    .collect(BitSet::new, BitSet::set, BitSet::or)
    .nextClearBit(0);

如果“正”表示“大于零”，则必须使用 i > 0和nextClearBit(1) 。该解决方案还将支持并行处理。

了解 Java API 提供的现有算法和数据结构是此类任务的必要条件。以及知道什么是真正不存在的、需要自己实现的。