给定一个范围，我必须计算数组中数字的频率。给定的解决方案有效吗？
#include<iostream.h>
int main()
{
int a[10]={1,2,3,5,2,3,1,5,3,1};
int i;
int c[10]={0};
for(i = 0 ; i < 10 ; i++)
c[a[i]]++;
for(i=0;i<10;i++)
cout<<i<<": "<<c[i]<<endl;
return 0;
}
该算法的运行时间为 O(n)，但占用了 O(n) 的额外空间。我可以做得更好吗？
谢谢！
#include<iostream.h>
int main()
{
int a[10]={1,2,3,5,2,3,1,5,3,1};
int i;
int c[10]={0};
for(i = 0 ; i < 10 ; i++)
c[a[i]]++;
for(i=0;i<10;i++)
cout<<i<<": "<<c[i]<<endl;
return 0;
}
The running time of the Algorithm is O(n) but its taking an extra space of O(n). Can I do better?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
取决于对您来说重要的事情 - 您可以创建一个花费 O(n^2) 时间但 O(1) 空间的算法（使用两个循环，请参阅下面的代码），但您无法将时间复杂度提高到 O(n ）。
O(1) 空间的另一种可能性是对数组进行就地排序，然后遍历一次，使用就地合并排序的时间复杂度应该是 O(n log n)。
Depends on what is important to you - you can create an algorithm taking O(n^2) time, but O(1) space (using two loops, see code below), but you can't improve time complexity below O(n).
Another possiblity for O(1) space would be an in-place sort of the array and then traversing this once, which should have time complexity O(n log n) using in-place merge sort.
不，你不能。这是你能做的最好的事情了。
No you can't. That's the best you can do.
什么是“高效”？向我们展示您的性能要求和性能测量。然后我们可以告诉您它是否有效。在那之前，这是一个悬而未决的问题，有很多错误答案，但没有正确答案。
到目前为止，答案是正确的，只有“高效”一词意味着“尽可能快地运行”。
也许您有一台速度很快但内存很少的计算机。
你总是可以让一段代码运行得更快，或者使用更少的内存或更少的磁盘空间或更少......如果它不够“高效”，我见过有人手工组装以使其更快。通常这是浪费时间和精力。优化尚未分析的代码是一场傻瓜游戏。
What is "efficient"? Show us you performance requirements and performance measurements. Then we can tell you if it's efficient. Until then this is a wide open question with lots of wrong answers and no right answer.
The answers thus far are correct only the word 'efficient' means 'runs as fast possible'.
Maybe you have a fast computer with little RAM.
You can always make a piece of code run faster or use less memory of less disk space or less.... if it is not 'efficient' enough, I have seen guys hand craft assembly to make it faster. Usually it's a waste of time and effort. Optimizing code that has not been profiled is a fools game.
如果所有数字都在 1 到 n 范围内，则可以以 O(n) 时间复杂度和 O(1) 空间复杂度完成。
如果存在索引 X 和数组 A，使得 A[X]=Y，则将 N 添加到索引 Y 处的值。因此 A[Y] 变为 A[Y]=original+N。继续下去，值的形式将是 (original+KN)，其中 k>=0。要检索原始元素，我们可以执行 (original+KN)%N，因为 (x+kn)%n=x 并且可以通过 (原值+KN)/N。
If all the numbers are in range 1 to n then in can be done in O(n) time complexity and O(1) space complexity.
if there is an index X and array A such that A[X]=Y then add N to the value present at index Y.So A[Y] becomes A[Y]=original+N. Continuing this ,values will be of form (original+KN) where k>=0.To retrieve original element we can do (original+KN)%N since (x+kn)%n=x and count can be found by (original+KN)/N.