广东峰凌建设有限公司网站,北京网站设计制作多少钱,青岛十大外贸公司,广告推广系统18.6 设计一个算法#xff0c;给定10亿个数字#xff0c;找出最小的100万个数字。假定计算机内存足以容纳全部10亿个数字。 解法#xff1a; 方法1#xff1a;排序 按升序排序所有的元素#xff0c;然后取出前100万个数#xff0c;时间复杂度为O(nlog(n)) 方法2#xff…18.6 设计一个算法给定10亿个数字找出最小的100万个数字。假定计算机内存足以容纳全部10亿个数字。 解法 方法1排序 按升序排序所有的元素然后取出前100万个数时间复杂度为O(nlog(n)) 方法2大顶堆 我们可以使用大顶堆来解题。首先为前100万个数字创建一个大顶堆 然后遍历整个数列将每个元素插入大顶堆并删除最大的元素。 遍历结束后我们将得到一个堆刚好包含最小的100万个数字。这个算法的时间复杂度为O(nlog(m))其中m为待查找数值的数量。 方法3选择排序算法假如你可以改变原始数组 在计算机科学中选择排序是个很有名的算法可以在线性时间内找到数组中第i个最小或最大元素。 如果这些元素各不相同则可以在预期的O(n)时间内找到第i个最小的元素。 转载于:https://www.cnblogs.com/wuchanming/p/4362389.html
