经典笔试——找到数组第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. 其他解法

堆排序方法