java - Java程序因某些测试用例超时而失败

我在Hackerrank上练习。好吧，这个问题非常简单，我在此处通过示例输入将其附加。当我使用自定义输入运行到本地计算机时，其工作正常。但是，当我在其在线平台上运行时，有时2个，有时3个测试用例因超时异常而失败。代码在下面，任何人都可以提出需要改进的地方？



这是解决方案

public static void main(String[] args) {
        int k = 3;
        List<Integer> marks = new ArrayList<Integer>();
        marks.add(20);
        marks.add(20);
        marks.add(40);
        marks.add(60);
        marks.add(20);
        marks.add(10);
        marks.add(0);
        marks.add(100);
        System.out.println(numofPrizes(k, marks));
    }
    public static int numofPrizes(int k, List<Integer> list) {
        // Write your code here
        Collections.sort(list, Collections.reverseOrder());
        List<Integer> str = new ArrayList<Integer>();
        AtomicInteger rank = new AtomicInteger(0);
        AtomicInteger count = new AtomicInteger(0);
        list.stream().forEach(x -> {
            if(!str.contains(x)){
                rank.getAndIncrement();
            }
            if(rank.get() <= k && x > 0){
                count.getAndIncrement();
            }
            str.add(x);
//          System.out.println("mark " + x + " rank " + rank.get() + " count " + count.get() );
        });
        return count.get();
    }

输出：

mark 100 rank 1 count 1
mark 60 rank 2 count 2
mark 40 rank 3 count 3
mark 20 rank 4 count 3
mark 20 rank 4 count 3
mark 20 rank 4 count 3
mark 10 rank 5 count 3
mark 0 rank 6 count 3
3

最佳答案

您可以在可读性和性能方面进行改进的某些代码部分可能是：


您可以使用List.sort在List元素上精确使用API

list.sort(Collections.reverseOrder());

您的代码中涉及昂贵的方法调用，通常是O（n2）操作，即

if(!str.contains(x))

此操作可能很有效，即在HashSet上执行时的O（n），但是您还可以在其他add开销上进行一些优化：

Set<Integer> str = new HashSet<>();

if (str.add(x)) {
    rank++; // or the use of getAndIncrement
}

在函数式编程结构中，您宁愿想到counting值，同时以相反的顺序对其进行排序，然后在执行相应计数之和时限制输入中的等级截止

private static int numofPrizes(int k, List<Integer> list) {
    Map<Integer, Integer> valueToCount = list.stream()
            .filter(mark -> mark != 0)
            .collect(Collectors.groupingBy(Function.identity(),
                    Collectors.collectingAndThen(Collectors.counting(), Long::intValue)));

    return valueToCount.entrySet().stream()
            .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
            .limit(k)
            .mapToInt(Map.Entry::getValue)
            .sum();
}

请注意，再次groupingBy here is an O(n) operation和这个完整的逻辑可以将我合并到一个管道中，如下所示：

private static long numOfPrizes(int k, List<Integer> list) {
    return list.stream()
            .filter(mark -> mark != 0)
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
            .entrySet().stream()
            .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
            .limit(k)
            .mapToLong(Map.Entry::getValue)
            .sum();
}