我要招人

去企业版

首页 > 试题广场 >

寻找第K大

[编程题]寻找第K大

热度指数：382144 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

要求：时间复杂度 $O(nlogn)$ ，空间复杂度 $O(1)$

数据范围： $0\le n \le 1000$ ， $1 \le K \le n$ ，数组中每个元素满足 $0 \le val \le 10000000$

示例1

输入

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

输出

示例2

输入

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

输出

说明

去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9

算法知识视频讲解

Javascript

Xinleidebaby

function findKth( a ,  n ,  K ) {
    // write code here
    let b=a.sort((a,b)=>b-a)
  return b[K-1]
}

发表于 2022-08-04 08:20:55 回复(0)

Javascript

牛客871274733号

function findKth( a ,  n ,  K ) {
     const arr = a.sort((a,b)=>b-a)
     return arr[K-1]
}
module.exports = {
    findKth : findKth
};

发表于 2022-07-05 15:42:39 回复(0)

Javascript

funny_soul

连用快排都超时？？？？

发表于 2022-04-27 13:18:33 回复(0)

Javascript

summer_swilder

function findKth( a , n , K ) {
a.sort((a, b) => b - a);
return a.splice(K - 1, K)[0]; // splice返回数组
}

发表于 2022-04-26 23:03:08 回复(0)

Javascript

牛小扭

/**
 * 
 * @param a int整型一维数组 
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */
 function findKth( a ,  n ,  K ) {
    // write code here
    return a.sort((a,b) => b-a)[K-1]
}
module.exports = {
    findKth : findKth
};

发表于 2022-04-22 14:19:47 回复(0)

Javascript

一世长安_

function findKth( a ,  n ,  K ) {
    // write code here
    a.sort((a,b) => a -b)
    return a[n - K]
}
module.exports = {
    findKth : findKth
};

有点太简单了

发表于 2022-04-07 22:01:11 回复(0)

Javascript

牛客38466221号

function findKth( a ,  n ,  K ) {
    return a.sort((a,b)=>b-a)[K-1]
}
module.exports = {
    findKth : findKth
};

发表于 2022-01-20 10:25:41 回复(0)

Javascript

prall1024

function findKth( a ,  n ,  K ) {
  function partion(a, lf, rt) {
    const flag = a[lf]
    while (lf < rt) {
      while (a[rt] <=flag && lf < rt) rt--
      if (lf < rt) a[lf++] = a[rt]
      while (a[lf] > flag && lf< rt) lf ++
      if (lf < rt) a[rt--] = a[lf]
    }
    a[lf] = flag
    return lf
  }
    
  let lf = 0, rt = a.length - 1
  let pivot = partion(a, lf, rt)
  while (pivot !== K-1) {
    if (pivot < K-1) {
      lf = pivot+1
    } else {
      rt = pivot-1
    }
    pivot = partion(a, lf, rt)
  }
  return a[pivot]
}

发表于 2022-01-01 00:00:51 回复(0)

Javascript

美英

/**
 * 
 * @param a int整型一维数组 
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */
function findKth( a ,  n , k  ) {
    // write code here
    a.sort((i,j)=>{
        return j-i;
    });
    return a[k-1];
}
module.exports = {
    findKth : findKth
};

发表于 2021-11-10 11:24:56 回复(0)

Javascript

小王子zzzzzzz

function findKth( a , n , K) {
const newArr = a.sort((a,b) => a-b)
return newArr[a.length - K]
}

发表于 2021-11-10 10:27:03 回复(0)

Javascript

飞牛cz

function findKth( a , n , K ) {
// write code here
a.sort(function(prev,next){
return next-prev;
});
return a.splice(K-1,1);
}
module.exports = {
findKth : findKth
};

发表于 2021-10-10 15:03:10 回复(0)

Javascript

xhxhsadsf

/**
*
* @param a int整型一维数组
* @param n int整型
* @param K int整型
* @return int整型
*/
function findKth( a , n , K ) {
// write code here
quick(a,0,a.length-1,a.length-K);
console.log(a);
return a[a.length-K];
}
function quick(a,left,right,k)
{
let mid=quicksort(a,left,right);
if(k<mid&&mid>left){
quick(a,left,mid-1,k);
}
if(k>mid&&mid<right){
quick(a,mid+1,right,k);
}
if(k===mid){
return
}
}
function quicksort(a,left,right)
{
let item=a[left];
while(left<right){
while(left<right&&a[right]>=item) right--;
a[left]=a[right];
while(left<right&&a[left]<=item) left++;
a[right]=a[left];
}
a[left]=item;
return left;
}
module.exports = {
findKth : findKth
};

发表于 2021-10-07 15:50:25 回复(0)

Javascript

TarsWANG

/**
 * 
 * @param a int整型一维数组 
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */
function findKth( a ,  n ,  K ) {
    // write code here
  function quickSort (a, L, R) {
    if (L >= R) return
    let i = L
    let j = R
    let p = a[i]
    while(i < j) {
      while(i < j && a[j] >= p) {
        j--
      }
      if(i < j) {
        a[i++] = a[j]
      }
      while(i < j && a[i] < p) {
        i++
      }
      if(i < j) {
        a[j--] = a[i]
      }
    }
    a[i] = p
    quickSort(a, L,i - 1)
    quickSort(a, i + 1, R)
  }
  quickSort(a, 0, a.length-1)
  return a[n - K]
}
module.exports = {
    findKth : findKth
};

发表于 2021-09-26 10:58:42 回复(0)

Javascript

狗力

function findKth( a , n , K ) {
return a.sort((a,b)=>b-a)[K-1]
}
🤣

发表于 2021-09-25 17:45:28 回复(0)

Javascript

牛客690471417号

搞不懂这里的n有啥用

发表于 2021-08-04 22:34:11 回复(0)

JavaScript

王志晗

Javascript(Node 12.18.2)

function findKth( a ,  n ,  K ) {
    // write code here
    if(n==0 || K>n)
        return [];
    quickSort(a,0,n-1);
    return a[n-K];
}
function quickSort(a, l, r){
    if(l>=r) return;
    let i=l, j=r, flag=a[i];
    while(i<j){
        while(i<j && a[j] > flag)
            j--;
        while(i<j && a[i] <= flag)
            i++;
        swap(a, i, j);
    }
    swap(a, i, l);
    quickSort(a, l,i-1);
    quickSort(a, i+1, r);
}
var swap = (a, i, j)=>{
    if(a.length == 0) return;
    let temp = a[j];
    a[j] = a[i];
    a[i] = temp;
};
module.exports = {
    findKth : findKth
};

发表于 2021-04-18 18:05:24 回复(0)

JavaScript

IPzzzi

function sortN(c,d){
    return c - d;
}
function findKth( a ,  n ,  K ) {
    // write code here
    a.sort(sortN);
    return a[n-K];
}

发表于 2021-04-12 23:01:39 回复(0)

JavaScript

splwany

function findKth( a ,  n ,  K ) {
    return quickfind(a, 0, n - 1, K);
}
function quickfind(a, left, right, k) {
    let i = left, j = right, pivot = a[left];
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    
    const deltaK = k - right + i - 1;
    if (deltaK === 0) return pivot;
    else if (deltaK > 0) return quickfind(a, left, i - 1, deltaK);
    else return quickfind(a, i + 1, right, k);
}

发表于 2021-04-03 10:57:54 回复(0)