输出前k大的数（分治算法）

刺骨的言语ヽ痛彻心扉 2023-03-01 09:28 42阅读 0赞

给定一个数组，统计前k大的数并把前k大的数从小到大输出来。  
输入：  
10  
4 5 6 9 8 7 1 2 3 0  
5  
输出：  
9  
8  
7  
6  
5  
程序代码：

#include <iostream>
    using namespace std;
    int js(int,int);
    int a[100001];
    int main(){ 
    	int n,k;
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	js(1,n);
    	cin>>k;
    	for(int i=1;i<=k;i++){ 
    		cout<<a[i]<<endl;
    	}
    	return 0;
    } 
    int js(int l,int r){     //快速排序，也可以用sort()函数代替 
    	int i,j,mid;
    	i=l;
    	j=r;
    	mid=a[(l+r)/2];
    	do{ 
    		while(a[i]>mid) i++;
    		while(a[j]<mid) j--;
    		if(i<=j){ 
    			int t;
    			t=a[i];a[i]=a[j];a[j]=t;
    			i++;
    			j--;
    		}
       	  } while(i<=j);
       	  if(l<j) js(l,j);
       	  if(r>j) js(i,r);
       	  return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTEwMDgz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTEwMDgz_size_16_color_FFFFFF_t_70]: /images/20230209/a7b11e8e52274071ad6234a7b4dee988.png

发表评论取消回复

表情：

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

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

相关阅读

相关找前k大个数的方法

找前k大个数的方法 1. 小堆法步骤复杂度 2. 快速选择算法步骤复杂度 3. 分治法

短命女/ 2024年03月27日 18:49/ 0 赞/ 144 阅读

相关【题解】使用分治法找出第K大的数（递归+分治）

题目描述输入n个数，求其中第k小的数。（要求采用分治法完成，不建议采用完整的排序）输入要求第一行包含两个整数n和k；n<1000，1<=K<=n 第二行包

àì夳堔傛蜴生んèń/ 2023年10月01日 20:48/ 0 赞/ 101 阅读

相关输出最大的数

/有三个整数a,b,c，由键盘输入，输出其中最大的数/ include <stdio.h> int main(){ int a,b,c,d,

怼烎@/ 2023年07月10日 08:24/ 0 赞/ 65 阅读

相关输出前m大的数

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

水深无声/ 2023年06月15日 06:55/ 0 赞/ 87 阅读

相关五大常用算法 | 分治算法

一、基本概念在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…

水深无声/ 2023年06月05日 08:24/ 0 赞/ 93 阅读

相关输出前k大的数（分治算法）

给定一个数组，统计前k大的数并把前k大的数从小到大输出来。输入： 10 4 5 6 9 8 7 1 2 3 0 5 输出： 9 8 7 6

刺骨的言语ヽ痛彻心扉/ 2023年03月01日 09:28/ 0 赞/ 43 阅读

相关 c++分治算法解决众数问题

众数问题 Description 给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S=\{1，2，2，

野性酷女/ 2022年11月18日 04:57/ 0 赞/ 323 阅读

相关输出前k大的数

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

Love The Way You Lie/ 2022年10月28日 14:28/ 0 赞/ 227 阅读

相关算法题目——第K大的数

题目链接：[剑指offer.76][offer.76] 思路：使用 priority\_queue 构建优先队列，这里注意要构建大顶堆，使less； pop() 弹

Myth丶恋晨/ 2022年09月15日 12:45/ 0 赞/ 216 阅读

相关求前K小的数和第K小的数

求前K小的数和第K小的数 1. 前K小的数（堆排序实现） include<iostream> include<algorithm> inclu

落日映苍穹つ/ 2022年08月06日 13:19/ 0 赞/ 244 阅读