时间戳

首页 > 解决方案 > 如何处理大数组/列表

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

问题描述

最近我尝试做代码任务。我经常以数组作为输入来执行任务，您需要解决以下问题：找到数组中不会出现的最小正整数等。我可以轻松处理小数组，但是当我汇总代码并通过测试获取摘要时，包括具有> 1000（或10 000）元素的数组我几乎总是有运行时错误。

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

大多数情况下，我尝试将数组转换为 List，如下所示：

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

有时我会使用过滤器，如您所见，有时我会在需要时使用 distinct/sort。但是我仍然有很多运行时错误。

我会很高兴提供一些如何处理它的提示。

@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% 的性能，因为：“TIMEOUT ERROR Killed。达到硬限制：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) 算法复杂度。如何解决？

标签： javaruntime-errorjava-stream

解决方案

首先，您必须问自己是否真的需要一个List<Integer>需要装箱的设备，或者一个int[]数组是否也足以完成您的任务。

所以

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

会更有效率。但是如果你真的需要 a ，你仍然应该在装箱值之前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))您正在调用filtera Stream<Integer>，传递 aPredicate<Integer>而不是 anIntPredicate并且实现别无选择，只能将 an 传递Integer给该代码。

类似的事情适用于sort; Integer当应用于原始类型数据而不是对象时，它的效率更高。有类似的潜力distinct，但是 afaik 这并没有在当前的实现中实现。

然后你必须自己实现更好的算法，这就是挑战的全部内容。

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

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

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

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

推荐阅读