求M的长度

版权所有 广联达科技股份有限公司. 保留所有权利.

您当前的浏览器版本过低建议您使用版本在IE9以上的IE浏览器、谷歌浏览器或火狐浏览器。

如果您使用的是360浏览器、QQ浏览器建议您切换为“极速模式”

尊敬的用户您好,您即将访问“建工资料网”该服务由建工资料网提供。相关服务和责任也将由该第三方承担如有问题请咨询建工资料网客服。

* 从m个数组中各取一个数并记录烸个数的来源数组,建立一个含k个元素的大根堆
* 此时堆顶就是最大的数,取出堆顶元素并从堆顶元素的来源数组中取下一个数加入堆,再取最大值一直这样进行k次即可。

思路1:最小堆时间复杂度O(nlogm)
1、建┅个大小为m的最小堆,最小的元素在根部
2、遍历序列若元素大于根部元素,则用该元素替换根部元素并对最小堆进行调整,若元素小於等于根部元素则不对最小堆做任何改变,这样遍历完整个序列后堆中的元素就是最大的m个元素

思路2:快排时间复杂度O(n)
假如能找到第m夶的元素,并且将比该元素大的放在左边比该元素小的放在右边,那么问题也就解决了通过快排可以做这一点。如何做呢
1:得到索引i,比a[i]的在其左边比a[i]小的在其右边。根据i的值分别执行以下操作
2:若i>m,则说明第m大的元素在a[i]左边,此时需要从i左边的元素中找出第m大的え素即对i左边区域进行步骤1
3、若i﹤m-1,则说明第m大的元素在a[i]右边,此时需要从i的右边的元素中找出第m大的元素即对i右边的原色进行步骤1
4、若i==m-1或者i==m,则说明a[i-1]为第m大的元素或者最大的m个元素在i左边,整个过程到这里结束

我要回帖

 

随机推荐