java - 为什么 8 种情况中有 2 种出现运行时错误？

Question

我已完成 Hackerrank's "Birthday Cake Candles" challenge并已通过使用以下代码对数组进行排序的 8 个测试用例中的 6 个，然后增加 max int 出现的频率并打印该值:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int numCandles = in.nextInt();
        int height[] = new int[numCandles];
        for(int height_i=0; height_i < numCandles; height_i++){
            height[height_i] = in.nextInt();
        }

        //Option 2: Sort the array, then count the number that are highest.
        Arrays.sort(height);
        int max = height[height.length - 1];
        int index = height.length - 1;
        int freq = 0;
        while(height[index] == max) {
            freq++;
            index--;
        }
        System.out.println(freq);
    }
}

它没有通过测试用例 #6 ( input ) 或测试用例 #7。简而言之，测试用例 #6 是 int 999999 出现 100,000 次，测试用例 #7 是 int 1 出现 100,000 次。两者的预期输出都应该是 100000。

我认为它可能会遇到运行时错误，因为我在数组上调用的排序方法以及数组试图一遍又一遍地对相等值的整数进行排序？谁能解释为什么我的代码不适用于这两个测试用例？

Answer 1

当输入中的所有值都相同时(如您所包含的示例输入中所示)，此循环中的条件将为 true，直到 index 减少到 -1，此时您将收到 ArrayIndexOutOfBoundsException:

while(height[index] == max) {
    freq++;
    index--;
}

给循环条件添加范围检查，例如:

while (index >= 0 && height[index] == max) {

通过此更改，该解决方案将通过所有测试。但这是一个低效的解决方案。您对输入进行排序以减少 while 循环中的迭代次数。但排序是一个 O(n log(n)) 操作，比使用 O(n) 的简单过滤要慢。例如:

int numCandles = in.nextInt();
int heights[] = new int[numCandles];
int m = Integer.MIN_VALUE;
for (int i = 0; i < numCandles; i++) {
    heights[i] = in.nextInt();
    m = Math.max(m, heights[i]);
}

final int max = m;
long freq = IntStream.of(heights).filter(x -> x == max).count();
System.out.println(freq);