如何处理大数组/列表

Question

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

有时我使用filter，如您所见，有时如果需要，我使用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();
    }
}

我的代码：

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

首先，您必须问自己是否真的需要列表 （需要装箱），或者int[]数组是否也足以完成任务。

所以

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

会更有效率。但是，如果您确实需要列表 ，那么在对值进行装箱之前，您仍然应该做尽可能多的工作，即。

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

这样，只对匹配的int值进行装箱，而不是对所有值进行装箱。这是一个流实现本身无法执行的优化，因为当您使用.boxed().filter(c->(c>-1001&&c<1001))时，您是在流 上调用filter，传递一个谓词 而不是intpredicate，实现别无选择，只能向该代码传递一个整数。

类似的事情也适用于sort；当应用于基元类型数据时，它比integer对象更有效。distinct也有类似的潜力，但afaik当前的实现没有实现这一点。

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

求数组中不包含的最小正整数的一个解决方案是

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

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