整数无序数组求第K大数

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();
    }
}

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

int main(){
    int a[100], k, n=0;
    while(true){
        scanf("%d", &a[n++]);
        if(getchar()=='\n')
            break;
    }
    scanf("%d", &k);
    for(int i=0;i<n-1;i++)
        for(int j=0;j<n-i-1;j++)
            if(a[j]<a[j+1])
                swap(a[j], a[j+1]);
    printf("%d\n", a[k-1]);
    return 0;
}

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;
}

python3解法

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

import sys

class heap(object):
    def __init__(self):
        self.length=0
        self.arr=None
    def build_heap(self,arr):
        self.arr=arr
        self.length=len(arr)
        for i in range(len(arr)-1,-1,-1):
            self.heapify(i,len(arr))
    def heapify(self,now,length):
        if now>=length:
            return
        l,r=now*2+1,now*2+2
        idx=now
        if l<length and self.arr[now]>self.arr[l]:
            now=l
        if r<length and self.arr[now]>self.arr[r]:
            now=r
        if idx!=now:
            self.arr[idx],self.arr[now]=self.arr[now],self.arr[idx]
            self.heapify(now,length)


if __name__=='__main__':
    nums=[int(a) for a in input().split()]
    k=int(input())
    h=heap()
    h.build_heap(nums[:k])
    while k<len(nums):
        if h.arr[0]<nums[k]:
            h.arr[0]=nums[k]
            h.heapify(0,h.length)
            k+=1
        else:
            k+=1
    print(h.arr[0])

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] str = sc.nextLine().split(" ");
        int k = sc.nextInt();
        int len = str.length;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        
        for (int x : arr) {
            if (minHeap.size() < k) {
                minHeap.offer(x);
            } else {
                if (minHeap.peek() < x) {
                    minHeap.poll();
                    minHeap.offer(x);
                }
            }
        }
        System.out.println(minHeap.peek());
    }
}

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
int main(){
    priority_queue<int,vector<int>,greater<int>> pq; // 小根堆
    vector<int> arr;
    int ele;
    while(cin >> ele){
        arr.push_back(ele);
        if(getchar() == '\n') break;
    }
    int k ;
    cin >> k;
    for(int i = 0;i < arr.size();i++){
        pq.push(arr[i]);
        if(pq.size() > k) pq.pop();
    }
    printf("%d",pq.top());
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] S =bf.readLine().split(" ");
        int[] a = new int[S.length];
        for(int i = 0;i < S.length;i++){
            a[i] = Integer.valueOf(S[i]);
        }
        int k = Integer.parseInt(bf.readLine());
        Arrays.sort(a);
        System.out.println(a[a.length-k]);
    }
}

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

vector<int>nums;

int main(){
    int temp;
    while(cin>>temp)
        nums.push_back(temp);
    int k = nums.back();
    nums.pop_back();//这里为什么将最后一个元素删除?
    int size = nums.size();
    if(k>=size){
        cout<<"输入的k错误"<<endl;
        return -1;
    }else{
        sort(nums.begin(),nums.end());
        cout<<nums[size - k]<<endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
 
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int[] arr = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        System.out.print(sort(arr, 0, arr.length - 1,arr.length - in.nextInt()));
    }
     
    public static int sort(int[] array, int left, int right,int k){
        int key = array[left];
        int i = left, j = right;
        while (i < j){
            while (key <= array[j] && i < j){
                j--;
            }
            while (key >= array[i] && i < j){
                i++;
            }
            if (i < j){
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        array[left] = array[i];
        array[i] = key;
        if(k == i)
            return array[i];
        if(k > i)
            return sort(array, i + 1, right,k);
        else
            return sort(array, left, i - 1,k);
    }
}

我用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])