在一个无序数组中，求最小的第 k 个数。
解法一：排序
时间复杂度：O(N logN)
def find_kth_num(arr, k):
if not arr: return
arr.sort()
return arr[k - 1]
解法二：大顶堆
- 建立一个大顶堆存在前 k 个数。
- 遍历数组，小于堆顶的数据，pop 出堆顶，push 出当前数
- 遍历完毕后，堆顶元素就是最小的第 k 个数
时间复杂度：O(N logK)
空间复杂度：O(K)
import heapq
def find_kth_num2(arr, k):
if not arr: return
# 大顶堆
heap = [-item for item in arr[:k]]
heapq.heapify(heap)
for i in range(k, len(arr)):
if -heap[0] > arr[i]:
heapq.heappushpop(heap,-arr[i])
return -heap[0]
解法三：二分法
时间复杂度：O(N)
跟快排一样，通过随机选取分割点，在概率上保证时间复杂度O(N)
最坏情况时间复杂度：$O(N^2)$
步骤：
- 随机选 x
- partition 分三段：< x , =x , > x 时间复杂度：O( N )
- 命中等于区域：直接返回。未命中：左 < x，左侧递归。右 > x，右侧递归
def find_kth_num1(arr, k):
if not arr: return
return process(arr, k - 1, 0, len(arr) - 1)
def process(arr, k, left, right):
index = random_range(left, right + 1)
less, more = partition(arr, index, left, right)
if less < k < more:
return arr[less + 1]
if less >= k:
return process(arr, k, left, less)
return process(arr, k, more, right)
def partition(nums, index, low, high):
less = low - 1
more = high + 1
x = nums[index]
while low < more:
if nums[low] < x:
less += 1
nums[less], nums[low] = nums[low], nums[less]
low += 1
elif nums[low] == x:
low += 1
else:
more -= 1
nums[more], nums[low] = nums[low], nums[more]
return less, more
def random_range(left, right):
return int(random.random() * (right - left)) + left
解法四：BFPRT
时间复杂度：O(N)，不需要概率保证就是 O(N)。
与解法二不同的是：本算法不是随机选取 x，而是通过一定的规则进行选取。
BFPRT算法整体步骤：
- 有讲究地选取 x
- partition 分三段：< x , =x , > x 时间复杂度：O( N )
- 等于区域命中：返回。未命中：左 < x，左侧递归。右 > x，右侧递归
有讲究地选取 x步骤
- 对 arr 数据进行分组：每 5 条数据一组。
- 对每组数据进行插入排序并获取小组内的上中位数
- 生成 m_arr 数组：m_arr 中的数据是每个小组的上中位数。
- 求出 m_arr 的上中位数作为 x：注意：m_arr 也是无序的，所以可以调用 process2(m_arr, int(len(m_arr) / 2), 0, len(m_arr) - 1)
def find_kth_num2(arr, k):
if not arr: return
return process2(arr, k - 1, 0, len(arr) - 1)
def process2(arr, k, left, right):
if left == right:
return arr[left]
x = median_of_medians(arr, left, right)
less, more = partition(arr, x, left, right)
if less < k < more:
return arr[less + 1]
if less >= k:
return process2(arr, k, left, less)
return process2(arr, k, more, right)
def partition(nums, x, low, high):
less = low - 1
more = high + 1
while low < more:
if nums[low] < x:
less += 1
nums[less], nums[low] = nums[low], nums[less]
low += 1
elif nums[low] == x:
low += 1
else:
more -= 1
nums[more], nums[low] = nums[low], nums[more]
return less, more
def median_of_medians(arr, left, right):
num = right - left + 1
offset = 0 if num % 5 == 0 else 1
# 分组
m_arr = [0] * (int(num / 5) + offset)
for i in range(len(m_arr)):
left_i = left + i * 5
right_i = left_i + 4
m_arr[i] = get_median(arr, left_i, min(right_i, right))
return process2(m_arr, int(len(m_arr) / 2), 0, len(m_arr) - 1)
def get_median(arr, left, right):
insertion_sort(arr, left, right)
sum = right + left
# 获取上中位数
mid = int((sum / 2) + (sum % 2))
return arr[mid]
# 插入排序：获取中位数需要有序
def insertion_sort(arr, left, right):
for i in range(left + 1, right + 1):
for j in range(i, left, -1):
if arr[j - 1] <= arr[j]: break
arr[j - 1], arr[j] = arr[j], arr[j - 1]