假设你有一架飞机,它的燃油含量很低.除非飞机下降3000磅的乘客重量,否则它将无法到达下一个机场.为了挽救最大数量的生命,我们想先把最重的人从飞机上扔掉.
哦,是的,飞机上有数百万人,我们希望找到最重的乘客的最佳算法,而不必整理整个列表.
这是我试图用C++编写代码的代理问题.我想按重量对乘客舱单做一个"partial_sort",但我不知道我需要多少元素.我可以实现自己的"partial_sort"算法("partial_sort_accumulate_until"),但我想知道是否有更简单的方法来使用标准STL.
问题:输入是一个(不一定是排序的)序列S = k1,k2,...,n个任意数的kn.考虑形式为min {ki,kj}的n 2个数的集合C,对于1 <= i,j <= n.提出一个O(n)时间和O(n)空间算法来找到C的中位数.
到目前为止,通过检查C的不同集合S,我发现C中S中最小数字的实例数等于(2n-1),下一个最小数字:(2n-3),依此类推,直到你只有一个最大数字的实例.
有没有办法使用这些信息来找到C的中位数？
我正在阅读O'Reilly Media出版的"坚果壳中的算法"一书,我正在阅读有关排序算法的部分,并找到了一个名为Median Sort的部分.由于我之前从未听说过它,而且我的CS3教科书(其中涵盖的算法)没有列出,我搜索了它并尝试在维基百科上查找并没有发现任何内容.如果有人可以提供我可以轻松查看算法的名称或者指向其他有关它的资源,我将不胜感激.谢谢.
另外,从我能说的算法来看,它基本上是Quicksort,除了它总是使用中值作为枢轴.通过中值我的意思是它似乎扫描项目数组并选择中间值作为枢轴,而不是选择数组中的中间项作为枢轴.此外,该书提到了与"中位数"类别相关的Blum-Floyd-Pratt-Rivest-Tarjan(BFPRT).
除了中位数算法算法之外,还有其他方法可以在最坏情况下的O(n)时间进行k选择吗？实施中位数中位数是否有意义; 我的意思是,性能优势是否足够实用？