首页 > 试题广场 >

整数无序数组求第K大数

[编程题]整数无序数组求第K大数
  • 热度指数:4219 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定无序整数序列,求其中第K大的数,例如{45,67,33,21},第2大数为45

输入描述:
输入第一行为整数序列,数字用空格分隔,如:45 67 33 21
输入第二行一个整数K,K在数组长度范围内,如:2


输出描述:
输出第K大的数,本例为第2大数:45
示例1

输入

45 67 33 21
2

输出

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

发表于 2019-01-23 19:53:35 回复(1)
可以用快速选择算法,均摊时间复杂度为O(N)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[strArr.length];
        for (int i = 0; i < arr.length; i++) arr[i] = Integer.parseInt(strArr[i]);
        int k = Integer.parseInt(br.readLine());
        System.out.println(quickSelect(arr, 0, arr.length - 1, k - 1));
    }
    private static int quickSelect(int[] arr, int left, int right, int k) {
        int p = partition(arr, left, right);     // 划分元素已经到了倒数第k,直接返回
        if(p == k)
            return arr[p];
        else if (p < k)
            return quickSelect(arr, p + 1, right, k);
        else
            return quickSelect(arr, left, p - 1, k);
    }
    
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int p = left;
        for(int i = left + 1; i <= right; i++){
            if(pivot < arr[i]){
                p ++;
                swap(arr, p, i);
            }
        }
        swap(arr, left, p);
        return p;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int cache = arr[i];
        arr[i] = arr[j];
        arr[j] = cache;
    }
}
也可以直接用小根堆解决,小根堆中只进入大的元素。
import java.lang.System;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int k = Integer.parseInt(br.readLine());
        int[] arr = new int[strArr.length];
        for(int i = 0; i < arr.length; i++) arr[i] = Integer.parseInt(strArr[i]);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i = 0; i < arr.length; i++){
            if(minHeap.size() < k){
                minHeap.offer(arr[i]);     // 容量还未到k,直接入堆
            }else{
                if(arr[i] > minHeap.peek()){
                    // 容量到达k,如果当前元素能干掉堆顶,就弹出堆顶,新元素入堆
                    minHeap.poll();
                    minHeap.offer(arr[i]);
                }
            }
        }
        System.out.println(minHeap.peek());    // 最终堆顶就是k个大元素中最小的,即第k大的元素
    }
}

编辑于 2021-11-28 13:24:48 回复(0)
#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;
}

发表于 2020-11-02 00:49:30 回复(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);
        }
    }
}
发表于 2019-02-28 00:50:40 回复(0)
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;
    }
}

编辑于 2019-01-11 15:02:04 回复(0)
#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;
}

这个题的输入 很让人难受,滴滴会出这种不规范的题吗?而且貌似测试用例是直接多次运行上述代码程序。总之很糟糕的体验,虽然是经典的TOP k问题,复杂度为O(nlogk),额外空间复杂度为O(1).
发表于 2018-08-23 14:40:28 回复(2)

python3解法

print(sorted(map(int, input().split()))[-int(input())])
发表于 2019-02-23 10:26:06 回复(0)
随机选择算法
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>

#define N 100010

int randPatition(int arr[],int left, int right) {
	int r = round(rand() * 1.0 / RAND_MAX * (right-left) + left);
	int t=arr[r];
	arr[r]=arr[left];
	arr[left]=t;
	int s=left;
	int e=right;
	while(s<e){
		while(s<e && arr[e]>t){
			e--;
		}
		arr[s]=arr[e];
		while(s<e && arr[s]<=t){
			s++;
		}
		arr[e]=arr[s];
	}
	arr[s]=t;
	return s;
}

int randSelect(int arr[],int left,int right,int k){
	if(left>=right){
		if(k==1){
			return arr[left];
		}else{
			return 0;//not found
		}
	}
	int p = randPatition(arr,left,right);
	int m = right - p + 1;
	if(m==k){
		return arr[p];
	}else if(m>k){
		return randSelect(arr,p+1,right,k);
	}else{
		return randSelect(arr,left,p-1,k-m);
	}
}

int main(){
	srand(unsigned(time(NULL)));
	int arr[N];
	int k;
	int n=0;
	while(~scanf("%d",&k)){
		arr[n++]=k;
	}
	n--;
	int res = randSelect(arr,0,n-1,k);
	printf("%d\n",res);
	return 0;
}


发表于 2023-04-20 16:33:17 回复(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());
    }
}

发表于 2022-09-17 14:56:21 回复(0)
#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());
}

小根堆
发表于 2022-02-08 01:09:49 回复(0)
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]);
    }
}

发表于 2021-12-28 11:09:27 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main (){
    int a;
    int num;
    vector <int> vec;
    while(cin>>a){
        if (cin.get() == '\n'){
            vec.push_back(a);
            break;
        }
        vec.push_back(a);
    }
    cin>>num;
    int n=vec.size();
    sort(vec.begin(),vec.end());
    cout<<vec[n-num];
    return 0;
}
发表于 2021-07-24 20:58:11 回复(0)
单调栈也可以用啊
发表于 2021-05-14 18:38:35 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
int main()
{
    int a;
    std::vector<int>s;
    while(std::cin>>a)
    {
        s.push_back(a);
    }
    int K=s[s.size()-1];
    s.pop_back();
    sort(s.begin(),s.end());
    std::cout<<s[s.size()-K]<<std::endl;
    s.clear();
    return 0;
}
发表于 2020-09-08 11:26:58 回复(0)
#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;
}

发表于 2020-08-28 19:20:50 回复(1)
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);
    }
}
这是最快解法吧!
发表于 2020-08-01 22:47:27 回复(0)
我用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");
}

发表于 2019-09-01 21:08:35 回复(0)
sxm头像 sxm
list=list(map(int,input().split()))
mm = int(input())  list.sort(reverse=True)
mm = mm-1 print(list[mm])

发表于 2019-08-26 19:17:49 回复(0)
我在想的是,这个输入是故意考我们处理这种问题的能力吗?
#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;
}


发表于 2019-08-09 23:33:52 回复(0)
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));
    }
}

发表于 2019-06-30 19:54:21 回复(0)