我正在尝试编写一个名为 Range 的类，它采用长度为n的整数(未排序)数组，仅包含范围从0到k的数字。
首先，我声明一个构造函数，它将通过计数排序算法预处理数组。
然后我想编写query()方法，该方法采用两个整数参数：a和b，它们形成从a到b的数字范围，并返回数组中具有给定范围内值的所有元素的总频率。
我的代码：
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()方法。
所以我的问题是：是否有可能通过HashMap实现query()的方法？
如果没有，还有什么替代方案？(注意：对于query()的时间复杂度应该是O(1)，而不在乎空间复杂度)。
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。
要在数组排序后以O(1) 为单位获取给定范围内(从a到b)中的元素数，不需要使用HashMap。相反，您可以通过将countingArray设置为实例变量来重用该。
这种方法还需要对排序稍作修改，以保持countingArray中的值完好无损。它是通过引入一个额外的变量来完成的。
请注意，避免改变输入是一种很好的做法，这就是为什么在我使用的代码中Arrays.copyOf()(如果您认为它与本练习无关，您可以将其删除)。
我已经将负责排序的逻辑从构造函数提取到一个单独的方法中。并引入了一种方法，该方法旨在计算数组中每个数字的累积计数(即具有从0到当前数字(包括)的值的元素的数量)。
因此，在Range实例上调用方法init()后，我们将能够通过查看存储在相应索引处的countingArray中的值来找到从a到b范围内的元素数量。这将产生O(1)的成本。
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
是的，为了缓存/预计算 query() 的返回值，您需要创建一个包含这两个值的组合键。最简单的方法是使用一个字符串，该字符串包含两个数字除以分隔符。分隔符很重要，否则复合键(21， 5) = "215" 和键 (2， 15) = "215"。使用分隔符时，将是"21;5"和"2;15"恭敬地。
private String key(int a, int b) {
return String.format("%d;%d", a, b);
}
然后，对于每个可能的组合键，您将值放入HashMap中。在 query(a， b) 方法中，您只是从 Map 中获取值。
public query(int a, int b) {
return map.get(key(a, b));
}
这种方法的缺点是创建此对象的开销非常大。