思路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左边,整个过程到这里结束