这是我昨天被问到的面试问题。哪位专家可以为我验证哪些说法是正确的？
如果我们有一个算法给出未排序的数组 3n不同的元素并计算两个值，x < y这样 n元素低于 x , n元素大于 y , n个元素在x之间和 y .
claims A) there is an algorithm of
O(n)average order for solving this problem.claims B) there is an algorithm of
O(n)order.claims C) with supposing
O(1)additional storage in addition to input array, we couldn't solve this problem in a poly time.claims D) each algorithm that solve this problem has
Omega(n lg n)order.
最佳答案
有O(n)时间解决方案，使用 selection algorithm .
找到 n+1第最小的元素和 2n th 最小的元素，这些是您要查找的必需元素。
选择算法的每次调用都是O(n)最坏的情况(中位数方法的中位数)，你需要其中的 2 个，所以复杂性仍然是 O(n) .
所以，
- 声明 B 是正确的，并且声明 A 也是正确的 - 此算法满足两个声明，其平均+最坏情况时间为
O(n). - 声明 C 是错误的，因为检查每一对的蛮力解决方案 元素和为每一对迭代数组需要 O(n^3) (多项式)时间和 O(1) 空间。
- 声明 D 是错误的，因为我们建议的算法在 O(n) 时间内运行，但解决了这个问题，所以有一个算法不是
Omega(nlogn)对于这个问题。
关于c++ - `3n` 不同的元素并找到两个值，`x < y`？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29140681/