算法：找出给定范围内数字的数量

Question

给定一个未排序的数字数组，其中可能存在重复项，预处理数组以便在给定范围内查找数字计数时，时间复杂度为O(1)。

例如，7,2,3,2,4,1,4,6。数字>=2且<=5的计数为5。(2,2,3,4,4)。

- user697417

---

“pre-processing” 这个部分是 O(1) 吗？我不认为这是可能的。我猜你的意思是预处理数组，以便结果可以在 O(1) 时间内计算给定条件的数字数量？ - Evan Teran

听起来像是作业？如果是，请打上标签。 - Rasmus Kaj

允许的可能最小/最大范围是什么？ - Mark B

Answer 1

对数组进行排序。对于已排序的每个元素，将该元素插入哈希表中，以元素的值作为键，以其在数组中的位置作为关联值。需要插入任何被跳过的值。

要查找范围内的项目数，请在哈希表中查找范围两端的值的位置，并从上限减去下限以找到范围的大小。

- Jerry Coffin

---

只有在输入数组从不稀疏的情况下才这样做，否则您可能会构建一个非常大的哈希映射表。或者在哈希映射表中存储每个元素的单独计数，并检查范围内的每个项。但是这样就不是O(1)了。 - pmr

该解决方案如何处理原始数组中的重复数字？对于OP的示例，您将如何区分第一个4和第二个4？ Translated text: 这个解决方案如何处理原始数组中的重复数字？对于OP的例子，你怎么区分第一个4和第二个4呢？ - DShook

@pmr：是的，如果您的输入非常稀疏，那么这将是非常浪费的。 @DShook：你有几个选择。两个明显的选择是跟踪第一个和最后一个位置，并跟踪相等元素的第一个位置和计数。 - Jerry Coffin

我可能错了，但我认为Jerry和我提出的基本上是相同的策略，如果不是完全相同的工具。在他的方案下，重复的数字不应该是一个问题，如果你只是从hash[upper]中减去hash[lower-1]，假设你始终将值在排序数组中的位置列在最右边的位置。 - jkerian

你可以通过分桶来节省一些空间。因此，如果输入范围是[l,u]，则查找最接近l和u的10的倍数，并将其用于哈希查找。然后进行另一个哈希查找，最多包含20个额外/缺失的项。 - Aryabhatta

没有理由使用哈希表，因为你要为范围[MIN，MAX]中的每个键插入一个键值对。只需使用数组即可。 - Chris Hopman

Answer 2

这似乎像是某些面试官喜欢问的巧妙问题之一，通常会提供一些提示来看你的思考方式。

不管怎样... 一种可能的实现方式是生成一个数字计数小于或等于列表索引的列表。例如，从您上面的列表中生成列表：0、1、3、4、6、6、7、8。然后，您可以通过从list[1]减去list[5]来计算2到5之间的数字数量。

- jkerian

---

即使如此，仅当数字本身来自有限范围（例如，如果它们保证适合常规int）时，它才是O（1）。 - Rasmus Kaj

严谨地说，如果您的列表类型不适合常规整数，则其并不会停止为O(1)...它完全停止工作（因为所需内存超过了许多/大多数系统的可寻址空间）。然而，该系统可以处理比int更大的值计数。由于生成的计数数组可以使用比uint更复杂的计数器，因此没有理由不这样做。 - jkerian

Answer 3

由于我们需要O(1)访问，所需的数据结构将需要占用大量内存。
使用哈希表，最坏情况下访问时间为O(n)。

我的解决方案：
构建一个二维矩阵。
数组 = {2,3,2,4,1,4,6} 数字范围为0到6，因此n = 7。
因此，我们必须创建nxn矩阵。
array[i][i]表示元素i的总计数。
因此，array[4][4] = 2（因为4在数组中出现了2次）
array[5][5] = 0
array[5][2] = >=2且<=5的数字的计数= 5

//preprocessing stage 1: Would populate a[i][i] with total count of element = i
a[n][n]={0};
for(i=0;i<=n;i++){
  a[i][i]++;
}

//stage 2
for(i=1;i<=n;i++)
  for(j=0;j<i;j++)
     a[i][j] = a[i-1][j] + a[i][i];
//we are just adding count of element=i to each value in i-1th row and we get ith row.

现在，(5,2)将查询a[5][2]并以O(1)的时间复杂度给出答案。

- rajya vardhan

Answer 4

int main()
{   
    int arr[8]={7,2,3,2,4,1,4,6};
    int count[9];
    int total=0;    

    memset(count,0, sizeof(count));

    for(int i=0;i<8;i++)
        count[arr[i]]++;

    for(int k=0;k<9;k++)
    {
        if(k>=2 && k<=5 && count[k]>0 )
        {
            total= total+count[k] ;     
        }
    }

    printf("%d:",total);
    return 0;
}

- Rajesh Ugemuge