你明白这个问题的意思吗
在小于线性时间的整数数组中查找顶部 log(n) 或顶部 sqt(n) 值。
如果你不这样做，这里是http://www.careercup.com/question?id=9337669的问题。
您能否帮助我理解这个问题，然后可能会得到解决。（虽然一旦我明白我也可能会解决它）
谢谢你的时间。
问问题
604 次
2 回答
6
对于非排序数组，复杂度是线性的，但可以通过观察 log(n) 和 sqrt(n) 都是单调增长函数来提高性能，因此 max(log(n),...) 也是log(max(n,...)) 和 sqrt 相同。
所以只需找到 max(n)（线性）并计算 log 和 sqrt。
于 2011-12-21T08:50:16.640 回答
3
假设数组没有排序，这个问题是Omega(n)，因为你需要读取所有元素[Omega(n)在未排序的数组中找到最大值是问题，这个问题并不比找到最大值更容易]。因此，它没有亚线性解决方案。
有O(n)[线性]解，使用选择算法
1. find the log(n) biggest element. //or sqrt(n) biggest element...
2. scan the array and return all elements bigger/equal it.
(*)如果数组包含欺骗，这个伪代码是不正确的，但是在第二步中修剪欺骗是相当容易的。
于 2011-12-21T08:18:54.443 回答