在o（1）的整数数组中找到i和j之间的元素数 [英] Finding the number of elements between i and j in an integer array in o(1)

问题描述

给出一个未排序的整数数组以及2个数字i和j，以使0< = i< = j< = C（常量表示MAX_INTEGER）可以对其进行什么样的预处理，这样您就可以能够找到在o（1）时间内i和j（包括两端）之间的数字数量。数组也可以有重复项。

Given an unsorted integer array and 2 numbers i and j such that 0 <= i <= j <= C(a constant say MAX_INTEGER) what kind of pre-processing can be performed on it so that you will be able to find the number of numbers between i and j(both inclusive) in o(1) time. The array can also have duplicates.

我曾考虑过为数组中的元素（空间o（C））以及$ b建立一个频率数组f []。 $ b用于累积频率（空间o（C））的另一个数组cf []。

I had thought of building a frequency array f[] for the elements in the array(space o(C)) and also another array cf[] for cumulative frequency(space o(C)).

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

So given i and j, i can look up the cumulative frequency array and do cf[j] - cf[i] - This will give the number of elements between i and j. To include i and j, look up the frequency array and add the values. ie cf[j] - cf[i] + f[i]+f[j] Time complexity will be o(1) * 4 = constant time.

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

The look up in the frequency array can be avoided by finding the previous non zero cf array element for both i and j in the respective direction. This will increase the time complexity but will reduce the space complexity.

想知道是否有更好的解决方案。

Wanted to know if there is a better solution for this problem.

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

Note - Values of i and j will be available to you only after the pre-processing is completed.

-Vijay

推荐答案

我无法想象在不使用O（C）额外空间的情况下如何在O（1）中执行此操作。

I can't imagine how you'd do this in O(1) without using O(C) additional space.

如果仅在启动时创建数组的排序副本，则可以非常轻松地在O（log n）中进行查找。 （O（n log n））。

You can do the lookup in O(log n) very easily if you just create a sorted copy of the array on startup. (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 。

Now, if the range of items in the array is relatively small, you could do it in O(max - min + 1) extra space and get O(1) lookup. But worst case, (max - min + 1) == C.

这篇关于在o（1）的整数数组中找到i和j之间的元素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！