如何以O(1)时间实现数组范围元素计数？HashMap可行吗？

问题核心 #

你需要的是基于计数排序预处理，实现O(1)时间的范围频次查询。用HashMap无法满足这个需求，因为HashMap的范围查询需要遍历区间内所有可能值，时间复杂度会退化为O(k)，不符合要求。

最优方案：前缀和数组 #

利用元素取值范围固定在0~k的特性，我们可以通过计数数组+前缀和数组实现O(1)查询：

1. 先统计每个元素的出现频次（计数数组）
2. 基于计数数组生成前缀和数组，prefixSum[i]表示0到i的元素总频次
3. 查询[a,b]范围时，结果为prefixSum[b] - (a>0 ? prefixSum[a-1] : 0)

预处理时间复杂度为O(n+k)，查询时间严格为O(1)。

修改后的完整代码 #

import java.util.Arrays;

public class Range {
    // 前缀和数组：prefixSum[i] 代表0~i区间内元素的总频次
    private int[] prefixSum;
    private int k;
    private int[] sortedArray; // 保留排序后的数组用于toString输出

    public Range(int[] a, int k) {
        this.k = k;
        int[] counterArray = new int[k + 1];

        // 第一步：统计每个元素的频次
        for (int num : a) {
            counterArray[num]++;
        }

        // 第二步：构建前缀和数组
        prefixSum = new int[k + 1];
        prefixSum[0] = counterArray[0];
        for (int i = 1; i <= k; i++) {
            prefixSum[i] = prefixSum[i - 1] + counterArray[i];
        }

        // 保留原逻辑生成排序后的数组（用于toString输出）
        sortedArray = Arrays.copyOf(a, a.length);
        int index = 0;
        for (int i = 0; i <= k; i++) {
            while (counterArray[i] > 0) {
                sortedArray[index++] = i;
                counterArray[i]--;
            }
        }
    }

    public int query(int a, int b) {
        // 处理边界：超出0~k范围的区间自动调整
        int lower = Math.max(a, 0);
        int upper = Math.min(b, k);

        if (lower > upper) {
            return 0;
        }

        return lower == 0 ? prefixSum[upper] : prefixSum[upper] - prefixSum[lower - 1];
    }

    @Override
    public String toString() {
        return Arrays.toString(sortedArray);
    }
}

测试代码：

public class Main {
    public static void main(String[] args) {
        int[] a = {13,12,13,1,2,0,0,1,3,4};
        Range range = new Range(a, 13);
        System.out.println(range); // 输出 [0,0,1,1,2,3,4,12,13,13]
        System.out.println(range.query(1, 4)); // 输出 5，符合预期
    }
}

为什么HashMap不可行？ #

HashMap仅能存储单个元素的频次映射，要计算[a,b]的总频次，你需要遍历a到b之间的所有整数，逐个从HashMap中取出频次累加。这个过程的时间复杂度是O(b-a+1)，最坏情况下是O(k)，无法达到O(1)的要求。

内容的提问来源于stack exchange，提问作者Caveira