首页 > 试题广场 >

寻找第K大

[编程题]寻找第K大
  • 热度指数：382144 时间限制：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
算法知识视频讲解
添加回答
Python
牛客96188058号头像 牛客96188058号
# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        # write code here
        a1=sorted(a,reverse=True)
        return a1[K-1]
发表于 2022-08-08 15:25:04 回复(0)
Python
牛客243695061号头像 牛客243695061号

这用例有问题吧
发表于 2022-08-04 19:34:48 回复(0)
Python
Carmack_X头像 Carmack_X
class Solution:
    def findKth(self, a, n, K):
        # write code here
        a.sort(reverse=True);
        return a[K-1]
发表于 2021-09-17 19:55:39 回复(0)
Python
Lee201908070018138头像 Lee201908070018138 
# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        if n>=K and K>=1:
            l = self.order(a)
            o=l[::-1]
            return o[K-1]
        else:
            return
    
    def order(self, tinput):
        if len(tinput) < 2:
            return tinput
        else:
            temp = tinput[0]
            less = [i for i in tinput[1:] if i <= temp]
            more = [i for i in tinput[1:] if i > temp]
            return self.order(less) + [temp] + self.order(more)

发表于 2021-07-18 14:34:12 回复(0)
Python
牛客590711274号头像 牛客590711274号 
class Solution:
    def findKth(self, a, n, K):
        a.sort(reverse =True)
        return a[K-1]

发表于 2021-07-12 18:28:51 回复(0)
Python
wengJJ头像 wengJJ
原始快排 
# -*- coding:utf-8 -*-

class Solution:
    def quick_sort(self,a,left,right,k):
        if left < right:
            mid = self.partition(a,left,right)
            if mid < k:
                self.quick_sort(a,left,mid-1,k)
            elif mid > k:
                self.quick_sort(a,mid+1,right,k)
            else:
                return a
                else:
                    return a
    def partition(self,a,left,right):
        pivot = left
        while left != right:
            while left < right and a[right] > a[pivot]:
                right -= 1
            while left < right and a[left] <= a[pivot]:
                left += 1
            if left < right:
                a[left],a[right] = a[right],a[left]
        a[pivot],a[left] = a[left],a[pivot] 
        return left
            
    def findKth(self, a, n, K):
        # write code here
        return self.quick_sort(a,0,n-1,n-K)[n-K]

根据所给K值进行剪枝优化 
# -*- coding:utf-8 -*-

class Solution:
    def quick_sort(self,a,left,right,k):
        mid = self.partition(a,left,right)
        if mid == k:
            return a[mid]
        elif mid > k:
            return self.quick_sort(a,left,mid-1,k)
        elif mid < k:
            return self.quick_sort(a,mid+1,right,k)
    def partition(self,a,left,right):
        pivot = left
        while left != right:
            while left < right and a[right] > a[pivot]:
                right -= 1
            while left < right and a[left] <= a[pivot]:
                left += 1
            if left < right:
                a[left],a[right] = a[right],a[left]
        a[pivot],a[left] = a[left],a[pivot] 
        return left
            
    def findKth(self, a, n, K):
        # write code here
        return self.quick_sort(a,0,n-1,n-K)


发表于 2021-06-04 22:42:50 回复(0)
Python
牛客280427523号头像 牛客280427523号
class Solution:
    def findKth(self, a, n, K):
        # write code here
        if(K>n):
            return []
        else:
            return sorted(a,reverse=True)[K-1]
发表于 2021-05-25 11:40:20 回复(0)
Python
林Lynn头儿头像 林Lynn头儿
class Solution:
    def findKth(self, a, n, K):
        # write code here
        return sorted(a[:n],reverse=True)[K-1]
发表于 2021-05-11 16:20:43 回复(0)
Python
XingyuXiong头像 XingyuXiong
这种优化不太好的程序反而能过，还是列表表达式性能比较好，这么做已经完成了对整个数组的快排
正常写topk理应是剪枝掉一半的，即不可能包含topk的那部分就不需要
# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        # write code here
        def quick_sort(nums,K):
            if len(nums)<=1:
                return nums
            pivot=nums[0]
            left=quick_sort([x for x in nums if x<pivot],K)
            right=quick_sort([x for x in nums if x>pivot],K)
            return left+[pivot]+right
        nums=quick_sort(a,K)
        return nums[n-K]

发表于 2021-04-20 16:24:14 回复(0)
Python
风卷尘沙起头像 风卷尘沙起 
class Solution:
    def findKth(self, a, n, K):
        # write code here
        low,high = 0,n-1
        return self.fastSort(a,K,low,high)
        
    def fastSort(self,a,k,low,high):
        mid = self.partition(a,low,high)
        if(mid+1==k):
            return a[mid]
        if(mid+1>k):
            return self.fastSort(a,k,low,mid-1)
        return self.fastSort(a,k,mid+1,high)
        
    def partition(self,a,low,high):
        mid = a[low]
        while(low<high):
            while(low<high and a[high]<=mid):
                high -= 1
            a[low]=a[high]
            while(low<high and a[low]>=mid):
                low+=1
            a[high]=a[low]
        a[low] = mid
        return low

发表于 2021-02-08 21:33:13 回复(0)
Python
chilly小胖胖头像 chilly小胖胖
class Solution:
    def findKth(self, a, n, K):
        # write code here
        if n<=1:
            return a[0]
        a=self.quick_sort(a,0,n-1,K)
        return a[n-K]
    def quick_sort(self,a,first,last,K):
        if first>last:
            return
        low=first
        high=last
        temp=a[first]
        while first<last:
            while first<last and a[last]>=temp:
                last-=1
            a[first]=a[last]
            while first<last and a[first]<temp:
                first+=1
            a[last]=a[first]
        a[first]=temp
        self.quick_sort(a,low,first-1,K)
        self.quick_sort(a,last+1,high,K)
        return a
发表于 2021-02-04 15:39:59 回复(0)
Python
chen_h1头像 chen_h1 
class Solution:
    def findKth(self, a, n, K):
        # write code here
        return sorted(a)[::-1][K-1]
发表于 2021-01-04 07:43:28 回复(0)
Python
Wen_myspace头像 Wen_myspace 
# 比较清晰易懂的Python完成
# -*- coding:utf-8 -*-
def partition(a, low, high):
    i = (low-1)         # index of smaller element
    pivot = a[high]     # pivot
    for j in range(low, high):
        if a[j] <= pivot:
            i = i+1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[high] = a[high], a[i+1]
    return (i+1)
def quickSort(a, low, high):
    if len(a) == 1:
        return a
    if low < high:
        pi = partition(a, low, high)
        quickSort(a, low, pi-1)
        quickSort(a, pi+1, high)

while True:
    try:
        x=input().replace(']', '')
        x=x.replace('[', '')
        x=list(x.split(','))
        k=int(x.pop())
        n=int(x.pop())
        a=list(map(int,x))
        quickSort(a, 0, n-1)
        a = a[::-1] #注意这里要求从大到小排列 我刚开始没有注意到
        print(a[k-1])
    except:break

发表于 2020-10-12 15:39:48 回复(0)
Python
李寻七头像 李寻七
#这大概是作弊吧
class Solution:
    def findKth(self, a, n, K):
        # write code here
        return sorted(a)[n-K]

发表于 2020-09-28 10:34:31 回复(1)
Python
sk8_wt头像 sk8_wt 
class Solution:
    def findKth(self, a, n, K):
        # write code here
        if n == 1:
            return a[0]
        a,index = self.fastorder(a,n)
        if index == K:
            return a[index-1]
        elif index < K:
            return self.findKth(a[index:], len(a[index:]), K-index)
        elif index > K:
            return self.findKth(a[:index-1], len(a[:index-1]), K)
            
    def fastorder(self,a,n):
        if n == 1:
            return a,n
        left = 0
        right = n-1
        val = a[0]
        while left<right:
            while left<right:
                if a[right]>val:
                    a[left] = a[right]
                    break
                else:
                    right -= 1

            while left<right:
                if a[left]<val:
                    a[right]=a[left]
                    break
                else:
                    left += 1
        a[left] = val
        return a,left+1
调了半天怎么都不对，最后发现题目要求是第K大，我写的是第K小，mmp
发表于 2020-09-08 11:51:49 回复(0)
Python
莫等闲201809292301189头像 莫等闲201809292301189
使用快排的策略，每次查找的partitionIndex与k进行比较    
 partitionIndex = self.partition(a, left, right)
if partitionIndex < k:
    return self.quickSort(a, partitionIndex + 1, right, k)
elif partitionIndex > k:
    return self.quickSort(a, left, partitionIndex - 1, k)
else:
    return a[partitionIndex]    

完整代码
class Solution:
    def findKth(self, a, n, K):
        # write code heren-K
        return self.quickSort(a, 0, n-1, n-K)

    def quickSort(self, a, left, right, k):
        partitionIndex = self.partition(a, left, right)
        if partitionIndex < k:
            return self.quickSort(a, partitionIndex + 1, right, k)
        elif partitionIndex > k:
            return self.quickSort(a, left, partitionIndex - 1, k)
        else:
            return a[partitionIndex]

    def partition(self, a, left, right):
        plag = left
        move = left + 1
        i = move
        while i <= right:
            if a[i] < a[plag]:
                a[i], a[move] = a[move], a[i]
                move += 1
            i += 1
        move -= 1
        a[plag], a[move] = a[move], a[plag]
        return move

编辑于 2020-08-31 01:19:49 回复(0)
Python
单恋一枝花头像 单恋一枝花
# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        temp=[]
        l=[]
        if n !=len(a):
            return False
        while(a):
            num=a[0]
            for i in a:
                if num<i:
                    num=i
            l.append(num)
            a.remove(num)
        for item in l:
            if item not in temp:
                temp.append(item)
        return temp[K-1]
发表于 2020-08-27 09:54:32 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

寻找第K大

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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