使用计数排序算法的一部分来返回 a 和 b 之间的元素数量

Question

我在一个关于计数排序算法的网站中发现了这个问题，这个问题是一个练习！我解决了这个问题，我想知道这是正确的吗？

锻炼： 利用计数排序算法的思想，提供一个算法，其中n个0到k范围内的整数，在O(1)时间内回答这n个元素中有多少个在区间[a,b]内？当然，您的算法应该处理 n 个元素，这些元素可以帮助您获取 a 和 b (0 ≤ a, b ≤ k) 之间的数字。这个基本过程应该在时间 θ (n + k) 内完成。

这是我的算法：

Algorithm Range(A,k,a,b)
{Consider C is the output array of PartOfCountingSort algorithm}
C<--PartOfCountingSort(A,k)
//finding the number of elements between a and b
numberOfElements<-- C[b]-C[a]+1
return numberOfElements
//end of the Range algorithm
------------------------------------
PartOfCountingSort(A,k)  // Theta(n+k)
OutPut: array C is the output of this algorithm
   for  i<-- 1 to k
      C[i]<-- 0
   for  j<-- 1 to A. length
      C[A[j]]<--C[A[j]]+1
   for  i<--2 to k
      C[i]<--C[i]+C[i-1]

Answer 1

它应该是

numberOfElements<-- C[b]-C[a - 1]

回想一下 C[i] = 小于或等于 i 的元素数量。您不想减去等于 a 的值。

您还应该处理 a = 0 以及 a = 1 的情况。