首页 > 试题广场 > 整数无序数组求第K大数
[编程题]整数无序数组求第K大数
给定无序整数序列,求其中第K大的数,例如{45,67,33,21},第2大数为45

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


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

输入

45 67 33 21
2

输出

45

python3解法

print(sorted(map(int, input().split()))[-int(input())])
发表于 2019-02-23 10:26:06 回复(0)
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 回复(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)
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)
输入为一行,最后一个数是K,

发表于 2019-05-02 15:30:23 回复(0)
#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函数的源码就是快排,直接拿来用
编辑于 2019-04-15 10:10:20 回复(0)
TT.头像 TT.

快排思想

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;
    }
}
编辑于 2019-04-07 20:18:11 回复(0)
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()

发表于 2019-03-09 21:30:28 回复(0)
//优先队列或者快排找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();
   

发表于 2019-02-25 21:06:00 回复(0)
#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;
}

发表于 2019-02-20 17:09:43 回复(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;
        }
    }

}

发表于 2018-11-19 22:02:00 回复(0)
#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;
}
牛客上面测试的:


我自己电脑看的结果是对的啊:

发表于 2018-09-13 17:18:44 回复(0)
用multiset容器就可以
发表于 2018-08-20 19:34:07 回复(0)
个人运行正常,还请大神多多指教。
利用python语言实现,最后进行排序,利用附属索引去的所需要的值

发表于 2018-08-20 17:27:06 回复(0)