[编程题]整数无序数组求第K大数

输入描述:
```输入第一行为整数序列，数字用空格分隔，如：45 67 33 21

输出描述:
`输出第K大的数，本例为第2大数：45`

输入

```45 67 33 21
2
```

```45
```

python3解法

``````print(sorted(map(int, input().split()))[-int(input())])
``````

```import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
public static void main( String[] args ) {
Scanner sc = new Scanner( System.in );
while( sc.hasNext() ) {
Scanner num = new Scanner( sc.nextLine() );
int k = sc.nextInt();
PriorityQueue<Integer> queue =
new PriorityQueue<>( (Integer i1, Integer i2)->i1-i2 );
for( int i = 0; i < k; i ++ )
queue.offer( num.nextInt() );
while( num.hasNextInt() ) {
int tmp = num.nextInt();
if( tmp > queue.peek() ) {
queue.poll();
queue.offer( tmp );
}
}
System.out.println( queue.peek() );
}
sc.close();
}
}
```

```import java.util.*;
import java.util.stream.Collectors;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] inArr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
ArrayList<Integer> nums = new ArrayList<Integer>();
for (int num : inArr) {
nums.add(num);
}
int k = sc.nextInt();
solve(nums, nums.size()-k+1);
System.out.println(ans);
}
private static int ans = -1;
private static void solve(ArrayList<Integer> arr, int k) {
ArrayList<Integer> left = new ArrayList<>();
ArrayList<Integer> right = new ArrayList<>();
int flagNum = arr.get(0);
for (int i=1; i!=arr.size(); i++) {
int cur = arr.get(i);
if (arr.get(i) <= flagNum) {
left.add(cur);
}
else {
right.add(cur);
}
}
if (left.size() == k-1) {
ans = flagNum;
return;
}
if (left.size() < k) {
solve(right, k-left.size()-1);
}
else if (left.size() >= k) {
solve(left, k);
}
}
}
```

```import java.util.Scanner;

/**
* 类似与求第k小的问题
* 求第k大相当于求第n-k+1小，n为数组长度
*
* 著名的BFPRT算法可保证在线性时间内得到结果。
* https://blog.csdn.net/qq_32767041/article/details/86099117
*
* 这里使用快速选择算法，这是一种基于快速排序的算法,
* 在实现上比BFPRT更简单。
* https://blog.csdn.net/qq_32767041/article/details/86300744
*
* @author wylu
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String[] strs = scanner.nextLine().split(" ");
int[] arr = new int[strs.length];
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.valueOf(strs[i]);
}
int k = scanner.nextInt();
System.out.println(arr[quickSelect(arr, arr.length - k + 1)]);
}
}

/**
* 查找第k小元素
* @param arr 无序数组
* @param k 目标第k小
* @return 成功：返回第k小元素的索引
*         失败：返回-1
*/
public static int quickSelect(int[] arr, int k) {
int left = 0, right = arr.length - 1, idx;
while (left <= right) {
idx = partition(arr, left, right);
if ((k - 1) == idx) return idx;
else if ((k - 1) > idx) left = idx + 1;
else right = idx - 1;
}
return -1;
}

/**
* 对给定的数组区间进行划分
* @param arr 数组
* @param left 区间下限，包含arr[left]
* @param right 区间上限，包含arr[right]
* @return 返回划分后，划分基准的索引
*/
private static int partition(int[] arr, int left, int right) {
int j = left - 1;
for (int i = left; i < right; i++) {
if (arr[i] <= arr[right]) swap(arr, i, ++j);
}
swap(arr, ++j, right);
return j;
}

private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
```

```#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int top_k(vector<int> & nums){
priority_queue<int,vector<int>,greater<int>> pq;
int i,j;
for(i=0;i<nums.back();++i)
pq.push(nums[i]);
for(j=i;j<nums.size()-1;++j)
if(nums[j]>pq.top()){
pq.pop();
pq.push(nums[j]);
}
return pq.top();
}

int main(void){
vector<int> nums;
int num;
while(cin>>num){
nums.push_back(num);
}
cout<<top_k(nums)<<endl;
}
```

```我用vs试了一下，以下代码是可以的，但是在这上面不成功。
#include <iostream>
using namespace std;

void BubbleSort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] < arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

int main()
{
int a, x;
int s[100];
for (int i = 0; i < 100; i++)
{
cin >> s[i];
if (cin.get() == '\n')
break;
}
cin >> x;
BubbleSort(s, 100);
a = s[x - 1];
cout << a << endl;
system("pause");
}```

```list=list(map(int,input().split()))
mm = int(input())  list.sort(reverse=True)
mm = mm-1 print(list[mm])```

```#include<bits/stdc++.h>
using namespace std;

int main(){
priority_queue<int, vector<int>, greater<int>> pq;
vector<int> nums;
int t;
while(cin >> t){
nums.push_back(t);
}
int k = nums[nums.size()-1];
for(int i = 0; i < nums.size()-1; i++){
if(pq.size() < k){
pq.push(nums[i]);
}else{
if(nums[i] > pq.top()){
pq.pop();
pq.push(nums[i]);
}
}
}
cout << pq.top() << endl;
}
```

```import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
List<Integer> list=new ArrayList<>();
while(sc.hasNext()){
list.add(sc.nextInt());
}
int n=list.get(list.size()-1);
list.remove(list.size()-1);
list.sort(new Comparator<Integer>(){
public int compare(Integer i2,Integer i1){
return i1-i2;
}
});
System.out.println(list.get(n-1));
}
}
```

#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b){
return a > b;
}
int main(){
int num[10010], n, i = 0, k;
while(cin >> n)
num[i++] = n;
k = num[i-1];
num[i-1] = -1;/*让原本k位置的数变成一个足够小的数，使其在从大到小排序中，永远是最小的
//那个，这样不至于影响前面的排列*/
sort(num, num+i, cmp);
cout << num[k-1];
}
sort函数的源码就是快排，直接拿来用

```import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] firstLine = sc.nextLine().split(" ");
int[] arr = new int[firstLine.length];
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(firstLine[i]);
}
int k = sc.nextInt();
System.out.println(findKMax(arr, 0, arr.length - 1, k - 1));
}
private static int findKMax(int[] arr, int left, int right, int k) {
int p = partition(arr, left, right);
if (p == k)
return arr[p];
else if (p < k)
return findKMax(arr, p + 1, right, k);
else
return findKMax(arr, left, p - 1, k);
}
private static int partition(int[] arr, int left, int right) {
int value = arr[left];
int p = left;
for (int i = left + 1; i <= right; i++) {
if (arr[i] > value) {
p ++;
swap(arr, p, i);
}
}
swap(arr, left, p);
return p;
}
private static void swap(int[] arr, int a, int b) {
int t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
}```

```def main():
num_list = list(map(int,input().split()))
k = int(input())
num_list.sort()
num_list.reverse()
print(num_list[k-1])

if __name__ == '__main__':
main()
```

```//优先队列或者快排找TOP K问题，我服了，输入根本没有两行，第一行最后一个输入的就是K值。。。。
//我真的佛了。。。。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
vector<int> vec;
int num;
while(cin>>num)
vec.push_back(num);
int K=vec.back();
vec.pop_back();
priority_queue<int,vector<int>,greater<int>> pq; //因为要找第K大，那么我们就要维护一个小顶堆
for(auto it:vec){
if(pq.size()<K) //未满，直接进入
pq.push(it);
else{
if(it>pq.top()){
pq.pop();
pq.push(it);
}
}
}
cout<<pq.top();

```

```#include "stdio.h"
#include <vector>
#include <iostream>
using namespace std;
int findPos(vector<int>& arr, int left, int right)
{
int flag = arr[left];
while(left<right)
{
while(left<right&&arr[right]>=flag)
right--;
arr[left] = arr[right];

while(left<right&&arr[left]<flag)
left++;
arr[right] = arr[left];
}
arr[left] = flag;
return left;
}
int main()
{
vector<int> arr;
int ele;
while(cin>>ele)
{
arr.push_back(ele);
if(getchar() == '\n')
break;
}
int k;
cin>>k;
k = arr.size()-k+1;
k--;
int begin = 0, end= arr.size()-1;
int pos = 0;
while(begin<end)
{
pos = findPos(arr, begin, end);
if(pos == k)
break;
else
{
if(pos>k)
end = pos-1;
else
begin = pos + 1;
}
}
cout<<arr[k]<<endl;
return 0;
}
```

```//快速排序，亲测对有重复元素的数组会有问题，需要加去重代码
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = null;
String strIn[] = {};
if(sc.hasNext()) {
str = sc.nextLine();
}
if(str!=null && str.trim().length()>0) {
strIn = str.split(" ");
}
int arr[] = new int[strIn.length];
int k = 0;
for(int i=0;i<strIn.length;i++) {
arr[i] = Integer.parseInt(strIn[i]);
}

if(sc.hasNext()) {
k=sc.nextInt();
}

int index = findKMaxInteger(arr, 0, arr.length-1, k);
System.out.println(arr[index]);

}

public static int findKMaxInteger(int array[],int low,int high, int findK){
int i = low;
int j = high;
int key = array[i];
while(i < j){
while(i < j && array[j] >= key) {
j--;
}
array[i] = array[j];

while(i < j && array[i] <= key) {
i++;
}
array[j] = array[i];
array[i] = key;
}
if(array.length-i < findK) {
return findKMaxInteger(array, low, i - 1, findK);
}else if(array.length-i > findK) {
return findKMaxInteger(array, i + 1, high, findK);
}else{
return i;
}
}

}

```

#include<stdio.h>

int main()
{
int array[100];
int i=0;
int m,n,k,t;
int max;
char y;

do
{
scanf("%d",&array[i]);
i++;
}while(y=getchar()!='\n');
scanf("%d",&k);
for(m=0;m<i;m++)
{
for(n=m;n<i;n++){
if(array[m]<array[n+1]){
t=array[m];
array[m]=array[n+1];
array[n+1]=t;
}

}

}

printf("%d\n", array[k-1]);
return 0;
}

`利用python语言实现，最后进行排序，利用附属索引去的所需要的值`

19条回答 3884浏览

通过挑战的用户

• 2019-10-19 13:13:04
• 2019-10-13 22:02:39
• 2019-10-12 12:09:42
• 2019-10-10 20:06:05
• 2019-10-09 16:10:10

相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题