gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 01:18:48 25 4
gpt4 key购买 nike

最近我尝试做一些 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) 算法复杂度。怎么解决?

最佳答案

首先,你要问自己是否真的需要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)) 时一样。您正在调用filterStream<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 > 0nextClearBit(1) 。该解决方案还将支持并行处理。

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

关于java - 如何处理大数组/列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58125252/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com