经典笔试——找到数组第k大或第k小的数

1. 问题

在未排序的数组中找到第k个最大的元素,找到数组排序后的第k个最大的元素

示例:

输入:

1
[3,2,3,1,2,4,5,5,6] 和 k=4

输出:4

2. 解题思路

类快速排序思想,找到数组中元素的位置,当分界点的索引为k-1的时候,它就是第k大元素,第k小的数只需找(组数长度+1-k)大的数即可。其时间复杂度应小于$O(n\log_2n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def findKthLargest(self,nums,k):
return self.findKthSmallest(nums,len(nums)+1-k)
def findKthSmallest(self,nums,k):
if nums:
pos = self.partition(nums,0,len(nums)-1)
if k>pos+1:
return self.findKthSmallest(nums[pos+1:],k-pos-1)
elif k<pos+1:
return self.findKthSmallest(nums[:pos],k)
else:
return nums[pos]
def partition(self,nums,l,r):
low = l
while l<r:
if nums[l] < nums[r]:
nums[l],nums[low] = nums[low],num[l]
low += 1
l += 1
nums[low],nums[r] = nums[r],nums[low]
return low

3. 其他解法

堆排序方法