热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

(Java)【深基9.例4】求第k小的数

【深基9.例4】求第k小的数一、题目描述输入nnn(1≤n


【深基9.例4】求第 k 小的数

一、题目描述

输入




n



n


n
(




1





n


<


5000000



1 \le n <5000000


1n<5000000





n



n


n
为奇数&#xff09;个数字





a


i




a_i


ai
&#xff08;




1






a


i



<



10


9




1 \le a_i <{10}^9


1ai<109
&#xff09;&#xff0c;输出这些数字的第




k



k


k
小的数。最小的数是第




0



0


0
小。

请尽量不要使用 nth_element 来写本题&#xff0c;因为本题的重点在于练习分治算法。


二、样例输入 #1

5 1
4 3 2 1 5

三、样例输出 #1

2

四、错误经历

使用了快速排序的标准模板&#xff0c;超时了

import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc &#61; new Scanner(System.in);
int n &#61; sc.nextInt();
int k &#61; sc.nextInt();
int[] a &#61; new int[n];
for (int i &#61; 0; i a[i] &#61; sc.nextInt();
}
quickSort(a, 0, n - 1);
System.out.println(a[k]);
}
public static void quickSort(int[] a, int low, int high) {
int i,j;
int temp,t;
if (low > high){
return;
}
i &#61; low;
j &#61; high;
//temp就是基准位
temp &#61; a[low];
while (i //先看右边&#xff0c;依次往左递减
while (a[j] >&#61; temp && j > i){
j--;
}
//再看左边&#xff0c;依次往右递增
while (a[i] <&#61; temp && i i&#43;&#43;;
}
//如果满足条件则交换
if (i t &#61; a[i];
a[i] &#61; a[j];
a[j] &#61; t;
}
}
//最后将基准为与i和j相等位置的数字交换
a[low] &#61; a[i];
a[i] &#61; temp;
//递归调用左半数组
quickSort(a,low,j - 1);
//递归调用右半数组
quickSort(a,j &#43; 1,high);
}
}

在这里插入图片描述

import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc &#61; new Scanner(System.in);
int n &#61; sc.nextInt();
int k &#61; sc.nextInt();
int[] a &#61; new int[n];
for (int i &#61; 0; i a[i] &#61; sc.nextInt();
}
Quick_Sort(a, 0, n - 1,k);
System.out.println(a[k]);
}
public static void Quick_Sort(int arr[], int begin, int end,int k){
if(begin > end)
return;
int tmp &#61; arr[begin];
int i &#61; begin;
int j &#61; end;
while(i !&#61; j){
while(arr[j] >&#61; tmp && j > i)
j--;
while(arr[i] <&#61; tmp && j > i)
i&#43;&#43;;
if(j > i){
int t &#61; arr[i];
arr[i] &#61; arr[j];
arr[j] &#61; t;
}
}
arr[begin] &#61; arr[i];
arr[i] &#61; tmp;
if(k &#61;&#61; i || k &#61;&#61; j) {
return;
} else if(k Quick_Sort(arr, begin, i-1,k);
}else if(k > j){
Quick_Sort(arr, j&#43;1, end,k);
}else {
Quick_Sort(arr, i, j,k);
}
}
}

在这里插入图片描述
直接使用了Arrays.sort( )&#xff0c;也超时了请添加图片描述

import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc &#61; new Scanner(System.in);
int n &#61; sc.nextInt();
int m &#61; sc.nextInt();
int[] a &#61; new int[n];
for (int i &#61; 0; i a[i] &#61; sc.nextInt();
}
Arrays.sort(a);
System.out.println(a[m]);
}
}

在这里插入图片描述

我废了&#xff0c;栓Q







推荐阅读
author-avatar
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有