快排-前m大元素

我不是女神ヾ 2022-05-16 06:55 162阅读 0赞

### 描述 给定一个数组包含n个元素，统计前m大的数并且把这m个数从大到小输 出。    ###

输入 第一行包含一个整数n，表示数组的大小。n < 100000。

第二行包含n个整数，表示数组的元素，整数之间以一个空格分开 。每个整数的绝对值不超过100000000。

第三行包含一个整数m。m < n。

输出 从大到小输出前m大的数，每个数一行。

排序后再输出，复杂度 O(nlogn)  
  
用分治（快排）处理：复杂度 O(n+mlogm)

思路：把前m大的都弄到数组最右边，然后对这最右边m个元素排序， 再输出  
  
关键 ：O(n)时间内实现把前m大的都弄到数组最右边

###    如何将前k大的都弄到最右边 ###

1）设key=a\[0\], 将key挪到适当位置，使得比key小的元素都在 key左边，比key大的元素都在key右边（线性时间完成）

2) 选择数组的前部或后部再进行 arrangeRight操作  
a = k done

a > k 对此a个元素再进行arrangeRigth(k)

a < k 对左边b个元素再进行arrangeRight(k-a)

### 时间复杂度： ###

将前m大的都弄到数组最右边的时间：  
  
T(n) = T(n/2) + a\*n

= T(n/4) + a\*n/2 + a\*n

= T(n/8) + a\*n/4 + a\*n/2 + a\*n

= ...

= T(1) + ... + a\*n/8 + a\*n/4 + a\*n/2 + a\*n < 2\*a\*n  
  
即 O(n)

### 代码实现 ###

### 很简单，看主要代码 ###

int a[N];
    int swap(int &a,int &b){
        int tmp=a;
        a=b;
        b=tmp;
        }
    void arrangeRight(int *a,int s,int e,int k){
        if(s>=e)
        return ;
        int t=a[s];
        int i=s,j=e;
        while(i!=j)
        {
            while(i<j&&t<=a[j])--j;
            swap(a[i],a[j]);
            while(j>i&&t>=a[i])++i;
            swap(a[i],a[j]);
        }
        int num=e-i+1;
        if(num==k) return;
        else if(num>k) arrangeRight(a,i+1,e,k);
        else if(num<k) arrangeRight(a,s,i-1,k-num);
    }

###     ###

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关快排

import java.util.Arrays; public class kuaiPai { public static void mai...

太过爱你忘了你带给我的痛/ 2024年04月17日 16:18/ 0 赞/ 88 阅读

相关 n个数里面找出最大的m个数字（快排思想）

分析：这个问题，我之前遇到的时候想到的解决方案是，最小堆解决方法。建立个数为m的最小堆，然后遍历n维护这个最小堆就可以了，算法的时间复杂度是n\log(m)。还是比较高效的算法

谁借莪１个温暖的怀抱￠/ 2022年07月17日 04:14/ 0 赞/ 183 阅读

相关快排

\include<stdio.h> int a\[1000\]; void quicksort(int first, int last)\{ i

阳光穿透心脏的1/2处/ 2022年06月13日 00:40/ 0 赞/ 225 阅读

相关 (快排实例)查询一个数组中第n大的元素

package cyd; / 查询一个数组中第n大的元素借用了快速排序的思想，我先选定一个标定值然后将数组等分小于这

短命女/ 2022年06月08日 08:42/ 0 赞/ 117 阅读

相关快排-前m大元素

描述给定一个数组包含n个元素，统计前m大的数并且把这m个数从大到小输出。输入第一行包含一个整数n，表示数组的大小。n < 100000。第二行包含n个整

我不是女神ヾ/ 2022年05月16日 06:55/ 0 赞/ 163 阅读

相关快排算法

include <bits/stdc++.h> using namespace std; void swap(int i, int

我就是我/ 2022年03月19日 04:52/ 0 赞/ 287 阅读

相关快排

public class Tester { public static int getIndex(int[] arr,int low,int

叁歲伎倆/ 2022年03月10日 09:18/ 0 赞/ 276 阅读

相关无敌快排

快速排序既然人家名称就叫快速排序，那么自然排序速度快，但是快也是相对而言的，不过大家知道就行了，这是哲学问题，万事万物都是相对的，原谅我也不咋的懂哲学，换一种不同的场景

谁践踏了优雅/ 2022年02月15日 03:28/ 0 赞/ 316 阅读

相关 golang 快排

package main import "fmt" / 快速排序快速排序复杂度 N (logN)

待我称王封你为后i/ 2022年01月12日 07:09/ 0 赞/ 298 阅读

相关 python 快排

def quick(lst, start, end): """ 快速排序复杂度 N (logN) 原理为有两个指针:

矫情吗；*/ 2022年01月12日 07:07/ 0 赞/ 327 阅读