在 O(1) 时间内获取排序数组中给定范围内的元素总数

Question

我正在尝试编写一个名为 Range 的类，它采用一个length 的整数数组（未排序），仅包含从到n范围内的数字。0k

首先，我声明一个构造函数，它将通过计数排序算法预处理数组。

然后我想编写query()接受两个整数参数的方法：a和，它形成从到 的b数字范围，并返回数组中具有给定范围内的值的所有元素的总频率。ab

我的代码：

import java.util.Arrays;
import java.util.HashMap;

public class Range {

    private int[] a;
    private int k;

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

        for (int i : a)
            counterArray[i]++;  // initialize counterArray

        for (int i = 0; i < counterArray.length; i++)
            while (0 < counterArray[i]) {
                a[index++] = i;
                counterArray[i]--;
            }   // end while()

        this.a = a;
        this.k = k;
    }   // end constructor()

    public int query(int a, int b) {
        HashMap<Integer, Integer> map = new HashMap<>(a);

    }   // end query()

    @Override
    public String toString() {
        return Arrays.toString(a);
    }   // end toString()
}

我选择HashMap数据结构是因为我需要在恒定时间O(1)query()内执行方法。

所以我的问题是：是否可以query()通过实现该方法HashMap？

如果没有，还有哪些替代方案？（注意： 的时间复杂度应该是O (1)query()，而不考虑空间复杂度）。

代码在main()：

int[] a = {13,12,13,1,2,0,0,1,3,4};
Range range = new Range(a, 13);
System.out.print(range); // prints [0,0,1,1,2,3,4,12,13,13] because array has been sorted

System.out.print(range.query(1, 4)); // calculating number of elements in the range [1, 4]

预期输出：

5   // elements 1,1,2,3,4 are within the range [1, 4]

解释：提供的参数query()是：a=1和b=4，因此要测试的值是1,2,3,4。输出应该是5因为有5元素：1,1,2,3,4。

Answer 1

要在数组排序后在O(1)a时间内获取给定范围（从到b包含）内的元素数量，不需要使用. 相反，您可以通过将其设为实例变量来重用它。HashMapcountingArray

此方法还需要对排序进行轻微修改，以便完整地保留值countingArray。这是通过引入一个附加变量来完成的。

请注意，避免改变输入是一个很好的做法，这就是为什么在我使用的代码中Arrays.copyOf()（如果您认为它与本练习无关，您可以将其删除）。

我已将负责排序的逻辑从构造函数中提取到一个单独的方法中。并引入了一种方法，该方法旨在计算数组中每个数字（即具有从当前数字（含）开始的值的元素的数量）的累积计数。0

因此，在调用init()实例的方法后Range，我们可以通过查看存储在相应索引中的值来找到从a到范围内的元素数量。这将花费O(1)。bcountingArray

public class Range {
    private int[] arr;
    private int[] counterArray;
    private int k;
    
    private Range(int[] arr, int k) { // constructor is not exposed
        this.arr = Arrays.copyOf(arr, arr.length);
        this.counterArray = new int[k + 1];
        this.k = k;
    }
    
    public static Range getInstance(int[] arr, int k) {
        Range range = new Range(arr, k);
        range.init();
        return range;
    }
    
    private void init() {
        sort();
        sumUpCount();
    }
    
    private void sort() {

        for (int i : arr) {
            counterArray[i]++;
        }

        int index = 0;
        int copy;
        for (int i = 0; i < counterArray.length; i++) {
            copy = counterArray[i];
            while (0 < counterArray[i]) {
                arr[index++] = i;
                counterArray[i]--;
            }
            counterArray[i] = copy;
        }
    }
    
    private void sumUpCount() {
        for (int i = 1; i < counterArray.length; i++) {
            counterArray[i] += counterArray[i - 1];
        }
    }
    
    public int query(int a, int b) {
        
        return a == 0 ? counterArray[b] :  counterArray[b] - counterArray[a - 1];
    }
}

main()

public static void main(String[] args) {
    int[] a = {13,12,13,1,2,0,0,1,3,4};
    Range range = Range.getInstance(a, 13);
    System.out.print(range.query(1,4));
}

输出：

5