leetcode 215：数组中的第K个最大元素(python)

╰+攻爆jí腚メ 2023-08-17 17:36 105阅读 0赞

# 题目 #

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: \[3,2,1,5,6,4\] 和 k = 2  
输出: 5  
示例 2:

输入: \[3,2,3,1,2,4,5,5,6\] 和 k = 4  
输出: 4  
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）  
链接：[LeetCode215. 数组中的第K个最大元素][LeetCode215. _K]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 解法一 (暴力排序法) #

*  思路  
    因为python是用list代替数组的，所以可以直接利用python提供的list.sort()函数对其进行排序后取对应大小的数
 *  代码

class Solution(object):
        def findKthLargest(self, nums, k):
            """ :type nums: List[int] :type k: int :rtype: int """
            nums.sort()
            return nums[-k]

*  结果  
    ![在这里插入图片描述][20191003210859453.png]

# 解法二(堆排序) #

*  思路  
    建立一个大小不超过k的小根堆，其根节点即为所求
 *  代码

class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
        
        	#利用自带库函数，一行解决
            #return heapq.nlargest(k, nums)[-1]
            
    		myheap=[]
            for num in nums:
                self.AddtoHeap(myheap,num)
                if len(myheap)>k:	#若堆的大小超过k，直接移除当前的根节点
                    myheap.pop(0)
            return myheap[0]
        
        def AddtoHeap(self,heap,num):
            lens,i=len(heap),0
            heap.insert(0,num)		#将新元素直接插入根节点位置
            while i<=lens//2:		#调整堆
                if i*2+1<=lens and heap[i*2+1]<heap[i*2]:
                    m=i*2+1
                else:
                    m=i*2
                if heap[m]<heap[i]:
                    temp=heap[m]
                    heap[m],heap[i]=heap[i],temp
                    i=m
                else:
                    break

*  结果  
    ![在这里插入图片描述][20191003221926368.png]

[LeetCode215. _K]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array
[20191003210859453.png]: /images/20230808/0aca40e4b60f45f1aa6b16f212efb123.png
[20191003221926368.png]: /images/20230808/9fcb880c0c964ba5aa71736a75ede575.png