java - 如何获取给定数组中最大值出现的次数

Question

我正在研究一个逻辑，我需要找到给定范围内最大值出现的次数。

示例:

例如，如果输入数组为[5, 4, 5, 3, 2] 现在我将提供一个表示索引位置 [0, 1, 2, 3, 4] 的查询数组

这些索引位置指示我的输入数组的起始位置。

预期输出为 [2,1,1,1,1]

说明:

索引 0 到 n 表示输入数组为 [5, 4, 5, 3, 2]。这里最大元素是5并且出现了2次

索引 1 到 n 表示输入数组为 [4, 5, 3, 2]。这里最大元素是5并且出现1次

索引 2 到 n 表示输入数组为 [5, 3, 2]。这里最大元素是5并且出现1次

索引 3 到 n 表示输入数组为 [3, 2]。这里最大元素是3并且出现1次

索引 4 到 n 表示输入数组为 [2]。这里最大元素是2并且出现1次

现在这是我想出的代码:

public static List<Integer> process(List<Integer> input, List<Integer> indexList) {
    // Write your code here
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < indexList.size(); i++) {
        int index = indexList.get(i);
        int max = Integer.MIN_VALUE;
        int count = 0;
        for (int j = index; j < input.size(); j++) {
            int data = input.get(j);
            if (data > max) {
                max = data;
                count = 1;
            } else if (data == max) {
                count++;
            }
        }
        list.add(count);
    }
    return list;
}

有没有更好的方法以更少的时间复杂度来做到这一点？

Answer 1

一个简单的 O(n) 算法就可以完成这项工作。只需在从数组末尾遍历时更新 max 值及其 count 即可。

Java代码:

public static List<Integer> process(List<Integer> data, List<Integer> indexList) {
    int n = data.size();
    int[]result = new int[n];
    int max = data.get(n - 1);
    int count = 1;
    result[n - 1] = 1;
    for(int i = n - 2; i >= 0; i--){
         if(max == data.get(i)){
            count++;
         }else if(max < data.get(i)){
            max = data.get(i);
            count = 1;
         }
         result[i] = count;
    }
    // Populate result
    List<Integer> list = new ArrayList<>();
    for(int i : indexList){
        list.add(result[i]);
    }
    return list;
}