找出数组中第 k 个小的元素
时间: 2024-03-28 21:15:03 浏览: 37
可以使用快速选择算法来找出数组中第 k 个小的元素。
快速选择算法的基本思路和快速排序类似,都是通过分治的思想来解决问题。具体步骤如下:
1. 选择一个数组中的元素作为枢纽元素(pivot)。
2. 将数组中小于枢纽元素的元素放在左边,大于枢纽元素的元素放在右边。
3. 如果枢纽元素的位置恰好等于 k-1,那么返回枢纽元素。
4. 如果枢纽元素的位置小于 k-1,那么在右边的子数组中继续查找第 k-1 小的元素。
5. 如果枢纽元素的位置大于 k-1,那么在左边的子数组中继续查找第 k-1 小的元素。
代码实现如下:
```python
def quick_select(nums, k):
if len(nums) == 1:
return nums[0]
pivot = nums[0]
left = [x for x in nums if x < pivot]
right = [x for x in nums if x > pivot]
equal = [x for x in nums if x == pivot]
if k <= len(left):
return quick_select(left, k)
elif k <= len(left) + len(equal):
return pivot
else:
return quick_select(right, k - len(left) - len(equal))
```
该算法的时间复杂度为 O(n),其中 n 是数组的长度。因为每次递归都至少能够排除掉一半的元素,所以总共最多需要递归 log n 次,所以时间复杂度为 O(n log n)。最坏情况下,每次递归只能排除掉一个元素,所以时间复杂度为 O(n^2)。但是最坏情况非常少出现,所以可以认为该算法的平均时间复杂度为 O(n)。