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

发布于 2024-09-06 11:44:48 字数 813 浏览 2 评论 0原文

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

锻炼: 利用计数排序算法的思想,提供一个算法,其中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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

_畞蕅 2024-09-13 11:44:48

它应该是

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 to a.

You should also handle the cases where a = 0 and maybe when a = 1 too.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文