2

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

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

所以给定 i 和 j，我可以查找累积频率数组并执行 cf[j] - cf[i] - 这将给出 i 和 j 之间的元素数。要包括 i 和 j，请查找频率数组并添加值。即 cf[j] - cf[i] + f[i]+f[j] 时间复杂度将为 o(1) * 4 = 常数时间。

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

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

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

-维杰

4

4 回答 4

2

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

如果您只是在启动时创建数组的排序副本，则可以非常轻松地在 O(log n) 中进行查找。(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.

于 2013-07-26T17:01:21.600 回答
1

这个怎么样，

首先，对整数数组进行排序。并创建一个哈希表，其中包含数组中每个唯一整数的键，并将值作为数组中的索引，该整数在排序数组中首先出现和最后出现，（因为 dup 是可能的）。哈希表的空间复杂度将是 O(n) 并且访问复杂度是恒定的，您必须相应地为哈希表分配空间。

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

于 2013-07-26T19:21:51.427 回答
-1 
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
于 2013-07-26T14:31:47.737 回答
-1

主意：

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

或者

1. first enter size of array    
2. then enter elements of array    
3. then query size    
4. then enter left, right

代码链接：HackerEarth

于 2018-10-30T18:05:03.543 回答