首页 > 试题广场 >

寻找第K大

[编程题]寻找第K大
  • 热度指数：380347 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
要求：时间复杂度 ，空间复杂度
数据范围：， ，数组中每个元素满足
示例1

输入

[1,3,5,2,2],5,3

输出

2
示例2

输入

[10,10,9,9,8,7,5,6,4,3,4,2],12,3

输出

9

说明

去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9
算法知识视频讲解
添加回答
C
牛客627928170号头像 牛客627928170号
#include<stdio.h>
 #include<stdlib.h>
void quickSort(int* a, int low, int high){//快速排序
    int i=low;
    int j=high;
    int key=a[i];
    while(i<j){
        while(i<j&&a[j]>=key) j--;
        a[i]=a[j];
        while(i<j&&a[i]<=key) i++;
        a[j]=a[i];
    }
    a[i]=key;

    if(low<i-1) quickSort(a,low,i-1);
    if(i+1<high) quickSort(a,i+1,high);
}
int findKth(int* a, int aLen, int n, int K ) {
    // write code here
    if(n==0) return *a;

    quickSort(a, 0, aLen-1);

    return a[aLen-K];

}
发表于 2025-09-09 20:59:21 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿
三行，继续秒你 
int cmp(const void *a, const void *b) {
    return *(int*)a > *(int*)b? -1: 1;
}
int findKth(int* a, int aLen, int n, int K ) {
    qsort(a, aLen, sizeof(int), cmp);
    return a[K-1];
}

编辑于 2024-03-20 11:10:55 回复(0)
C
喜欢划水头像 喜欢划水
void swap(int *a,int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int part(int *arr,int low, int high){
    int tmp = arr[high];
    int i = low -1;

    for (int j = low;j < high;++j) {
        if (arr[j] < tmp) {
            ++i;
            swap(&arr[i],&arr[j]);
        }
    }

    swap(&arr[i+1],&arr[high]);
   
    return i+1;
}

void qukicksort(int *arr,int low,int high){
    if (low < high) {
        int tmp = part(arr,low,high);
        qukicksort(arr,low,tmp -1);
        qukicksort(arr,tmp + 1,high);
    }
}

int findKth(int* a, int aLen, int n, int K ) {
    // write code here

    if (n < 1) {
        return 0;
    }

    qukicksort(a ,0,n-1);

    return a[aLen-K];
}
发表于 2023-11-30 11:13:38 回复(0)
C
帅奶哟。头像 帅奶哟。 
int privot(int a[], int low, int high);
void quicksort(int a[], int low, int high);

int findKth(int* a, int aLen, int n, int K ) {
    // write code here

    quicksort(a, 0, aLen-1);    //从小到大排序

    return a[aLen-K];   //返回第k大的
}

int privot(int a[], int low, int high){         //划分
    int p = a[low];
    while (low < high){
        while(low < high && a[high] >= p) high--;
        a[low] = a[high];
        while(low < high && a[low] <= p) low++;
        a[high] = a[low];
    }
    a[low] = p;
    return low;
}

void quicksort(int a[], int low, int high){     //快排
    if (low < high) {
        int pri = privot(a, low, high);
        quicksort(a, low, pri-1);
        quicksort(a, pri+1, high);

    }
}

发表于 2023-03-17 15:58:05 回复(0)
C
艾登皮洛斯头像 艾登皮洛斯
数据故意把快排的效率降到最低，建议直接sort
发表于 2022-07-27 22:32:49 回复(0)
C
聪敏的大白菜向光而行头像 聪敏的大白菜向光而行
/**
 * 
 * @param a int整型一维数组 
 * @param aLen int a数组长度
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#include <stdlib.h>
int cmp(const void *a, const void *b){
    return *(int *)b-*(int *)a;
}
int findKth(int* a, int aLen, int n, int K ) {
    // write code here
    qsort(a,aLen,sizeof(a[0]),cmp);
    return a[K-1];
}
发表于 2022-07-17 16:13:22 回复(0)
C
牛客339731127号头像 牛客339731127号
int fun(const void *a,const void *b){
    return *(int*)b - *(int*)a;
}
int findKth(int* a, int aLen, int n, int K ) {
    // write code here
    qsort(a,aLen,sizeof(int),fun);
    return a[K-1];
}
发表于 2022-04-16 21:24:49 回复(0)
C
好想找个工作呀头像 好想找个工作呀 
//快速排序
int Qsort(int *a,int low,int high){
    int t=a[high];
    while(low<high){
        while(low<high&&a[low]>=t){
            low++;
        }
        if(low<high){
            a[high]=a[low];
        }
        while(low<high&&a[high]<=t)
            high--;
        if(low<high)
            a[low]=a[high];
    }
    a[low]=t;
    return low;
}
 void Merge(int*a,int low,int high){
     if(low<high){
         int mid=Qsort(a,low,high);
         Merge(a,low,mid-1);
         Merge(a,mid+1,high);
     }
 }
int findKth(int* a, int aLen, int n, int K ) {
    // write code here
    Merge(a,0,n-1);
    return a[K-1];
    
}

发表于 2021-12-10 21:01:24 回复(1)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
#define findKth(a, aLen, n, k) __findKth(a, n, n - k, 0, n - 1)

void swap(int* a, int* b) { if (*a ^ *b) *a ^= *b, *b ^= *a, *a ^= *b; }
/**
 * 
 * @param a int整型一维数组 
 * @param aLen int a数组长度
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */
int __findKth(int* a, int n, int k, int left, int right) {  
  // recursion exit condition
  if (left == right) return *(a + left);
  
  int i = left, j = right, x = *(a + left + ((right - left) >> 1));
  do {
    while (*(a + i) < x) ++i;
    while (*(a + j) > x) --j;
    if (i <= j) swap(a + i++, a + j--);
  } while (i <= j);
  
  if (k <= j)      return __findKth(a, n, k, left, j);
  else if (i <= k) return __findKth(a, n, k, i, right);
  else             return __findKth(a, n, k, j + 1, i - 1);
}

发表于 2021-09-20 14:26:22 回复(0)
C
Hammer_2010头像 Hammer_2010
   int cmp(const void *a, const void *b)
   {
       return (*(int *)b -  *(int *)a);
   }

int findKth(int* a, int aLen, int n, int K ) {
    // write code here
    if(n <=0 || K < 1)
        return 0;
    //排序
    qsort(a, aLen, sizeof(int),cmp);

    //取下标
    return a[K-1];
}
时间复杂度nlogn怎么也能过？
发表于 2021-08-30 10:35:03 回复(0)
提交观点

问题信息

分治 堆
来自：网易2016实习研发工...
难度：
12条回答 49947浏览

热门推荐

通过挑战的用户

查看代码

相关试题

寻找第K大

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号