使用计数排序算法的一部分来返回 a 和 b 之间的元素数量
我在一个关于计数排序算法的网站中发现了这个问题,这个问题是一个练习!我解决了这个问题,我想知道这是正确的吗?
锻炼: 利用计数排序算法的思想,提供一个算法,其中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]
I have found this question in the one site which was about counting sort algorithm and this question was an exercise ! I solved this and I want to know that is this correct?
Exercise:
Use The idea of Counting Sort algorithm and provide an algorithm with n integer in the range 0 to k, in time O (1) replied that how many of these n elements are in the interval [a, b] ? Of course, your algorithm should process n elements that can help you take the numbers between a and b (0 ≤ a, b ≤ k) . This basic process should be in time Θ (n + k) .
this is my algorithm:
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]
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
它应该是
numberOfElements<-- C[b]-C[a - 1]
回想一下
C[i] = 小于或等于 i 的元素数量
。您不想减去等于a
的值。您还应该处理
a = 0
以及a = 1
的情况。It should be
numberOfElements<-- C[b]-C[a - 1]
Recall that
C[i] = number of elements lower than or equal to i
. You don't want to subtract those equal toa
.You should also handle the cases where
a = 0
and maybe whena = 1
too.