查找整数数组中的最高 log(n) 或最高 sqt(n) 值
您是否理解这个问题的含义？
在小于线性时间内查找整数数组中的最高 log(n) 或最高 sqt(n) 值。
如果您不这样做，请参阅以下问题 http://www.careercup.com/question?id =9337669。
您能否帮助我理解这个问题，然后可能会得到解决。 （虽然一旦我明白了，我也可能会解决它）
感谢您的时间。
Do you understand what this question means
Find top log(n) or top sqt(n) values in an array of integers in less than linear time.
If you don't, here is the question http://www.careercup.com/question?id=9337669.
Could you please help me in understanding this question and then may be get it solved. (Although once i understand i might get it solved too)
Thanks for your time.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对于非排序数组，复杂度是线性的，但可以通过观察 log(n) 和 sqrt(n) 都是单调增长函数来提高性能，因此 max(log(n),...) 也是log(max(n,...)) 与 sqrt 相同。
因此，只需找到 max(n) （线性）并计算 log 和 sqrt。
For non sorted array the complexity is linear, but it can be possible to improve the performance by observing that log(n) and sqrt(n) are both monotonic growing function, hence max(log(n),...) is also log(max(n,...)) and same for sqrt.
So just find max(n) (linearly) and calculate log and sqrt.
假设数组未排序，这个问题是
Omega(n)，因为您需要读取所有元素[在未排序数组中查找最大值是Omega(n)问题，这个问题并不比求 max 更容易]。因此，它没有次线性解。使用选择算法有
O(n)[线性]解决方案(*)如果数组包含重复项，则此伪代码不正确，但在第二步中修剪重复项相当容易。
Assuming the array is not sorted, This problem is
Omega(n), since you need to read all elements [finding max isOmega(n)problem in non-sorted array, and this problem is not easier then finding max]. So, there is no sublinear solution for it.There is
O(n)[linear] solution, using selection algorithm(*)This pseudo code is not correct if the array contain dupes, but trimming the dupes in a second step is fairly easy.