第k个数(c++, java)
2023-09-14 09:14:24 时间
第k个数(c++, java)
给定一个长度为 n的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式第一行包含两个整数 n 和 k。
第二行包含 n个整数(所有整数均在 1∼109 范围内),表示整数数列。
输出格式
输出一个整数,表示数列的第 k小数。
数据范围
1≤n≤100000,
1≤k≤n
输入样例:
5 3
2 4 1 5 3
输出样例:
3
提交代码
c++
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++; while (q[i] < x);
do j --; while (q[j] > x);
if (i < j) swap (q[i], q[j]);
}
quick_sort(q, l, j); quick_sort(q, j + 1, r);
}
int main(void)
{
int n, k;
scanf ("%d%d", &n, &k);
for (int i = 0; i < n; ++i) scanf ("%d", &q[i]);
quick_sort(q, 0, n - 1);
printf ("%d\n", q[k - 1]);
return 0;
}
java
import java.util.*;
public class Main{
private static int N = 100010;
private static int[] a = new int[N];
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
for(int i = 0; i < n; i++ ){
a[i] = scanner.nextInt();
}
int l = 0,r = n - 1;
//传入参数为下标k-1
System.out.println(quickSort(a,l,r,k-1));
}
public static int quickSort(int[] a,int l,int r,int k){
if(l == r){
return a[l];
}
int x = a[l + r >> 1];
int i = l - 1,j = r + 1;
while(i < j){
do{
i++;
}while(a[i] < x);
do{
j--;
}while(a[j] > x);
if(i < j){
swap(a,i,j);
}
}
if(k <= j){
return quickSort(a,l,j,k);
}else{
return quickSort(a,j+1,r,k);
}
}
public static void swap(int[] a,int i ,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
相关文章
- Java多线程详解_java支持多线程
- C++和Java中STL库入门[通俗易懂]
- java遍历数组取出最大值_求数组20个数的平均值
- 写java代码的软件_新手编写java代码使用什么软件
- Java 构造函数的详解
- 手机java程序_2020年最流行的Java开发技术
- java和c 就业,c++和java的区别和就业前景
- java无法获取服务器上路径,JAVA获取服务器路径的步骤
- 【说站】java程序计数器的使用注意
- java 数组转换_java数组转json
- 第十一届蓝桥杯——JAVA组真题
- Java-Response实现重定向
- java书店带商家商城书店多商家书店系统源码
- 【Android 内存优化】Android 原生 API 图片压缩原理 ( 图片质量压缩方法 | 查找 Java 源码中的 native 方法对应的 C++ 源码 )
- 【错误记录】生成 Java 文档错误 ( Xxx.java:xx: 错误: 编码GBK的不可映射字符 )
- Java Activiti6.0 spring5 SSM 工作流引擎 审批流程 java项目框架详解编程语言
- java 二叉查找树(增删改查操作)详解编程语言
- Java学习笔记之五java数组详解编程语言
- 深入理解Java之jvm启动流程详解编程语言
- 如何让JAVA程序实现一段时间等待详解编程语言
- Java中读取某个目录下的所有文件和文件夹详解编程语言
- 在Linux下搭建完美的Java开发环境(linux搭建java开发环境)
- 服务器实现Java远程访问Linux服务器(java远程linux)
- 删除Linux中的Java程序(linux删除java)
- 性Redis Java驱动:实现高效的过期性(redisjava过期)
- 实现Redis Java实现数据过期管理(redisjava过期)
- 机制使用Java实现Redis的过期机制(redisjava过期)
- 每周开源点评:云原生 Java、开源安全以及更多行业趋势
- 使用Java远程控制Linux 实现简单、高效的服务器管理(java控制linux)
- Linux下快速安装Java开发环境(linux安装java)
- java变量的区别浅析
- java删除文件夹下所有文件示例分享
- java自定义日期转化类示例