在o(1)中查找整数数组中i和j之间的元素数

Question

给定一个未排序的整数数组和两个数字i和j，使得0 <= i <= j <= C(一个常量，即MAX_INTEGER)可以对其执行什么样的预处理，以便您能够在o(1)时间内找到i和j(包括i和j)之间的数字的数量。该数组也可以有重复项。

我曾想过为数组中的元素构建一个频率数组f[] (空间o(C))，并为累积频率构建另一个数组cf[] (空间o(C))。

给定i和j，我可以查找累积频率数组并计算cfj - cfi -这将得到i和j之间的元素数。要包括i和j，请查找频率数组并将值相加。ie cfj - cfi + fi+fj时间复杂度为o(1) *4=常数时间。

通过找到i和j在相应方向上的先前非零cf阵列元素，可以避免在频率阵列中的查找。这将增加时间复杂度，但将降低空间复杂度。

我想知道这个问题是否有更好的解决方案。

注意-只有在预处理完成后，才能使用i和j的值。

-Vijay

Answer 1

我无法想象在不使用O(C)额外空间的情况下，如何在O(1)中做到这一点。

如果您只需在启动时创建数组的排序副本，则可以非常容易地在O(log )中进行查找。(O(n log n))。

然后查找就变成了：

Binary search to find the first occurrence of i
Binary search to find the last occurrence of j
result = position_of_j - position_of_i + 1

现在，如果数组中的项的范围相对较小，您可以在O(max - min + 1)个额外空间中执行此操作，并获得O(1)个查找。但最坏的情况是(max - min + 1) == C

Answer 2

这样如何？

首先，对整数数组进行排序。并创建一个哈希表，该哈希表具有数组中每个唯一整数的关键字，并且该值作为该整数在排序的数组中最先和最后出现的数组中的索引(因为dup是可能的)。如果哈希表的空间复杂度为O(n)，而访问复杂度是常数，则必须为哈希表分配相应的空间。

给定这些额外的数据结构，如果你想找出i和j之间的数字范围，从哈希表中得到i的第一个索引和j的最后一个索引，然后从后者中减去第一个得到结果。

Answer 3

Dim result() as integer
Dim C(1000) as integer
Dim Buff() as integer
Dim i as integer=50 
dim j as integer=450 
for count =0 to c.count-1
    if c(count)>i and c(count)<j then 
       dim length as integer=buff.count-1
       redim result(lenght+1)
       for buffcount=0 to buff.count
           result(buffcount)=buff(buffcount)
       next  
       result(result.count-1)=c(count)
       redim buff(result.lenght-1)
       buff=result
    end if 
next