03-高频算法题精讲-二分查找与排序
本章概述
二分查找和排序算法是面试中最基础也最重要的知识点。掌握二分查找的各种变体和经典排序算法，不仅能解决大量实际问题，还能在面试中展现扎实的算法功底。
本章涵盖：
- 二分查找的4种模板及其应用场景
- 快速排序、归并排序、堆排序的实现与优化
- 15+道LeetCode高频真题详解
- 完整的代码实现和复杂度分析
第一节：二分查找核心模板
1.1 二分查找的本质
二分查找不仅仅是在有序数组中查找元素，其本质是在单调性空间中寻找边界。只要能定义出"判定函数"，就可以使用二分查找。
1.2 模板一：查找精确值
def binary_search(nums: list[int], target: int) -> int:
"""
在有序数组中查找目标值
返回目标值的索引，不存在返回-1
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # 防止溢出
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 时间复杂度: O(log n)
# 空间复杂度: O(1)
Go语言实现：
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
1.3 模板二：查找左边界
查找第一个大于等于target的位置。
def binary_search_left(nums: list[int], target: int) -> int:
"""
查找第一个大于等于target的位置
"""
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
# 时间复杂度: O(log n)
# 空间复杂度: O(1)
1.4 模板三：查找右边界
查找最后一个小于等于target的位置。
def binary_search_right(nums: list[int], target: int) -> int:
"""
查找最后一个小于等于target的位置
"""
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
return left - 1
# 时间复杂度: O(log n)
# 空间复杂度: O(1)
1.5 模板四：实数二分
def binary_search_real(left: float, right: float,
check: callable, eps: float = 1e-6) -> float:
"""
实数域上的二分查找
left: 左边界
right: 右边界
check: 判定函数
eps: 精度要求
"""
while right - left > eps:
mid = (left + right) / 2
if check(mid):
right = mid
else:
left = mid
return left
# 时间复杂度: O(log(n/eps))
# 空间复杂度: O(1)
第二节：二分查找经典题目
2.1 LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置（中等）
题目描述： 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
解题思路： 使用两次二分查找，分别找左边界和右边界。
def searchRange(nums: list[int], target: int) -> list[int]:
"""
查找目标值的起始和结束位置
"""
def find_left(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
def find_right(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
return left - 1
if not nums:
return [-1, -1]
left_idx = find_left(nums, target)
# 目标值不存在
if left_idx == len(nums) or nums[left_idx] != target:
return [-1, -1]
right_idx = find_right(nums, target)
return [left_idx, right_idx]
# 测试
print(searchRange([5,7,7,8,8,10], 8)) # [3, 4]
print(searchRange([5,7,7,8,8,10], 6)) # [-1, -1]
# 时间复杂度: O(log n)
# 空间复杂度: O(1)
Go语言实现：
func searchRange(nums []int, target int) []int {
findLeft := func(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left
}
findRight := func(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] <= target {
left = mid + 1
} else {
right = mid
}
}
return left - 1
}
if len(nums) == 0 {
return []int{-1, -1}
}
leftIdx := findLeft(nums, target)
if leftIdx == len(nums) || nums[leftIdx] != target {
return []int{-1, -1}
}
rightIdx := findRight(nums, target)
return []int{leftIdx, rightIdx}
}
2.2 LeetCode 33. 搜索旋转排序数组（中等）
题目描述： 整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在某个下标 k 进行了旋转。例如，[0,1,2,4,5,6,7] 在下标 3 处旋转后变为 [4,5,6,7,0,1,2]。
解题思路： 旋转后的数组可以分为两部分有序数组。通过判断mid在哪一部分，来决定搜索方向。
def search(nums: list[int], target: int) -> int:
"""
在旋转排序数组中搜索目标值
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# 判断哪一部分是有序的
if nums[left] <= nums[mid]: # 左半部分有序
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半部分有序
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
# 测试
print(search([4,5,6,7,0,1,2], 0)) # 4
print(search([4,5,6,7,0,1,2], 3)) # -1
# 时间复杂度: O(log n)
# 空间复杂度: O(1)
2.3 LeetCode 153. 寻找旋转排序数组中的最小值（中等）
题目描述： 假设按照升序排序的数组在某个点上进行了旋转，找出其中最小的元素。
解题思路： 最小值一定在右侧无序的部分。通过比较mid和right的值来缩小范围。
def findMin(nums: list[int]) -> int:
"""
查找旋转数组中的最小值
"""
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# mid在左侧有序部分，最小值在右侧
if nums[mid] > nums[right]:
left = mid + 1
else: # mid在右侧，最小值可能是mid或在左侧
right = mid
return nums[left]
# 测试
print(findMin([3,4,5,1,2])) # 1
print(findMin([4,5,6,7,0,1,2])) # 0
# 时间复杂度: O(log n)
# 空间复杂度: O(1)
2.4 LeetCode 69. x 的平方根（简单）
题目描述： 实现 int sqrt(int x) 函数，计算并返回 x 的平方根。
解题思路： 在 [0, x] 范围内二分查找，找到最大的 k 使得 k^2 <= x。
def mySqrt(x: int) -> int:
"""
计算平方根的整数部分
"""
if x == 0:
return 0
left, right = 1, x
while left <= right:
mid = left + (right - left) // 2
if mid * mid == x:
return mid
elif mid * mid < x:
left = mid + 1
else:
right = mid - 1
return right # 返回小于等于的最大值
# 测试
print(mySqrt(4)) # 2
print(mySqrt(8)) # 2
# 时间复杂度: O(log n)
# 空间复杂度: O(1)
2.5 LeetCode 162. 寻找峰值（中等）
题目描述： 峰值元素是指其值大于左右相邻值的元素。给定一个数组 nums，找到峰值元素并返回其索引。
解题思路： 通过比较mid和mid+1，决定往哪个方向搜索。如果nums[mid] < nums[mid+1]，说明右侧一定有峰值。
def findPeakElement(nums: list[int]) -> int:
"""
查找峰值元素
"""
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[mid + 1]:
# 右侧一定有峰值
left = mid + 1
else:
# 左侧一定有峰值(包括mid)
right = mid
return left
# 测试
print(findPeakElement([1,2,3,1])) # 2
print(findPeakElement([1,2,1,3,5,6,4])) # 1 或 5
# 时间复杂度: O(log n)
# 空间复杂度: O(1)
2.6 LeetCode 875. 爱吃香蕉的珂珂（中等）
题目描述： 珂珂喜欢吃香蕉。有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k。
解题思路： 二分查找速度k，判断是否能在h小时内吃完。
def minEatingSpeed(piles: list[int], h: int) -> int:
"""
查找最小吃香蕉速度
"""
def can_finish(speed):
"""判断以speed速度能否在h小时内吃完"""
hours = 0
for pile in piles:
hours += (pile + speed - 1) // speed # 向上取整
return hours <= h
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if can_finish(mid):
right = mid # 可以吃完，尝试更慢的速度
else:
left = mid + 1 # 吃不完，需要更快的速度
return left
# 测试
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30
# 时间复杂度: O(n log m)，其中m是最大堆的大小
# 空间复杂度: O(1)
2.7 LeetCode 4. 寻找两个正序数组的中位数（困难）
题目描述： 给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2。请找出这两个正序数组的中位数。
解题思路： 在较短的数组上进行二分查找，找到合适的分割点，使得左半部分的最大值小于等于右半部分的最小值。
def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
"""
查找两个有序数组的中位数
"""
# 确保nums1是较短的数组
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
while left <= right:
# nums1的分割点
partition1 = (left + right) // 2
# nums2的分割点
partition2 = (m + n + 1) // 2 - partition1
# 左半部分的最大值
max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
# 右半部分的最小值
min_right1 = float('inf') if partition1 == m else nums1[partition1]
min_right2 = float('inf') if partition2 == n else nums2[partition2]
# 找到了正确的分割点
if max_left1 <= min_right2 and max_left2 <= min_right1:
# 总长度为偶数
if (m + n) % 2 == 0:
return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
# 总长度为奇数
else:
return max(max_left1, max_left2)
# nums1分割点太靠右
elif max_left1 > min_right2:
right = partition1 - 1
# nums1分割点太靠左
else:
left = partition1 + 1
return 0.0
# 测试
print(findMedianSortedArrays([1,3], [2])) # 2.0
print(findMedianSortedArrays([1,2], [3,4])) # 2.5
# 时间复杂度: O(log(min(m,n)))
# 空间复杂度: O(1)
第三节：快速排序
3.1 快速排序原理
快速排序是一种分治算法，通过选择一个基准元素（pivot），将数组分为两部分：小于基准的元素和大于基准的元素，然后递归地对两部分进行排序。
核心思想：
- 选择基准元素
- 分区（Partition）：将小于基准的元素移到左边，大于基准的移到右边
- 递归排序左右两部分
3.2 快速排序实现
def quickSort(arr: list[int]) -> list[int]:
"""
快速排序
"""
def partition(arr, low, high):
"""分区函数"""
pivot = arr[high] # 选择最后一个元素作为基准
i = low - 1 # i指向小于pivot的最后一个元素
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort_helper(arr, low, high):
if low < high:
# 获取分区点
pi = partition(arr, low, high)
# 递归排序左右两部分
quick_sort_helper(arr, low, pi - 1)
quick_sort_helper(arr, pi + 1, high)
quick_sort_helper(arr, 0, len(arr) - 1)
return arr
# 测试
print(quickSort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]
# 时间复杂度: 平均O(n log n)，最坏O(n^2)
# 空间复杂度: O(log n)递归栈空间
Go语言实现：
func quickSort(arr []int) []int {
partition := func(arr []int, low, high int) int {
pivot := arr[high]
i := low - 1
for j := low; j < high; j++ {
if arr[j] <= pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
}
var quickSortHelper func([]int, int, int)
quickSortHelper = func(arr []int, low, high int) {
if low < high {
pi := partition(arr, low, high)
quickSortHelper(arr, low, pi-1)
quickSortHelper(arr, pi+1, high)
}
}
quickSortHelper(arr, 0, len(arr)-1)
return arr
}
3.3 三路快排优化
当数组中有大量重复元素时，三路快排性能更好。
def threeWayQuickSort(arr: list[int]) -> list[int]:
"""
三路快排：将数组分为小于、等于、大于pivot三部分
"""
def three_way_partition(arr, low, high):
if low >= high:
return
pivot = arr[low]
lt = low # arr[low+1...lt] < pivot
gt = high # arr[gt...high] > pivot
i = low + 1 # arr[lt+1...i-1] == pivot
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[gt], arr[i] = arr[i], arr[gt]
gt -= 1
else:
i += 1
# 递归排序小于和大于pivot的部分
three_way_partition(arr, low, lt - 1)
three_way_partition(arr, gt + 1, high)
three_way_partition(arr, 0, len(arr) - 1)
return arr
# 测试
print(threeWayQuickSort([4, 2, 1, 3, 2, 4, 1, 3]))
# [1, 1, 2, 2, 3, 3, 4, 4]
# 时间复杂度: O(n log n)
# 空间复杂度: O(log n)
3.4 LeetCode 215. 数组中的第K个最大元素（中等）
题目描述： 在未排序的数组中找到第 k 个最大的元素。
解题思路： 使用快速选择算法，平均时间复杂度为O(n)。
def findKthLargest(nums: list[int], k: int) -> int:
"""
查找第k个最大元素
"""
def partition(left, right):
pivot = nums[right]
i = left
for j in range(left, right):
if nums[j] >= pivot: # 降序排列
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[right] = nums[right], nums[i]
return i
left, right = 0, len(nums) - 1
k_index = k - 1
while left <= right:
pivot_index = partition(left, right)
if pivot_index == k_index:
return nums[pivot_index]
elif pivot_index < k_index:
left = pivot_index + 1
else:
right = pivot_index - 1
return -1
# 测试
print(findKthLargest([3,2,1,5,6,4], 2)) # 5
print(findKthLargest([3,2,3,1,2,4,5,5,6], 4)) # 4
# 时间复杂度: 平均O(n)，最坏O(n^2)
# 空间复杂度: O(1)
第四节：归并排序
4.1 归并排序原理
归并排序是经典的分治算法，将数组分成两半，递归排序，然后合并两个有序数组。
核心步骤：
- 分解：将数组递归地分成两半
- 解决：递归地排序两个子数组
- 合并：将两个有序子数组合并成一个有序数组
4.2 归并排序实现
def mergeSort(arr: list[int]) -> list[int]:
"""
归并排序
"""
def merge(left, right):
"""合并两个有序数组"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return merge(left, right)
# 测试
print(mergeSort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]
# 时间复杂度: O(n log n)
# 空间复杂度: O(n)
原地归并排序（节省空间）：
def mergeSortInPlace(arr: list[int]) -> list[int]:
"""
原地归并排序
"""
def merge(arr, left, mid, right):
"""原地合并"""
temp = []
i, j = left, mid + 1
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp.append(arr[i])
i += 1
else:
temp.append(arr[j])
j += 1
temp.extend(arr[i:mid+1])
temp.extend(arr[j:right+1])
# 复制回原数组
for i, val in enumerate(temp):
arr[left + i] = val
def merge_sort_helper(arr, left, right):
if left < right:
mid = left + (right - left) // 2
merge_sort_helper(arr, left, mid)
merge_sort_helper(arr, mid + 1, right)
merge(arr, left, mid, right)
merge_sort_helper(arr, 0, len(arr) - 1)
return arr
# 时间复杂度: O(n log n)
# 空间复杂度: O(n)临时数组
4.3 LeetCode 88. 合并两个有序数组（简单）
题目描述： 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
解题思路： 从后往前填充，避免覆盖nums1中的元素。
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
"""
合并两个有序数组
"""
# 从后往前填充
p1 = m - 1 # nums1的指针
p2 = n - 1 # nums2的指针
p = m + n - 1 # 合并后的指针
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
# 如果nums2还有剩余
nums1[:p2+1] = nums2[:p2+1]
# 测试
nums1 = [1,2,3,0,0,0]
merge(nums1, 3, [2,5,6], 3)
print(nums1) # [1, 2, 2, 3, 5, 6]
# 时间复杂度: O(m + n)
# 空间复杂度: O(1)
4.4 LeetCode 148. 排序链表（中等）
题目描述： 给定链表的头结点 head ，请将其按升序排列并返回排序后的链表。
解题思路： 使用归并排序，先找到中点分割链表，然后递归排序并合并。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head: ListNode) -> ListNode:
"""
链表归并排序
"""
if not head or not head.next:
return head
# 快慢指针找中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 分割链表
mid = slow.next
slow.next = None
# 递归排序
left = sortList(head)
right = sortList(mid)
# 合并两个有序链表
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val < right.val:
curr.next = left
left = left.next
else:
curr.next = right
right = right.next
curr = curr.next
curr.next = left if left else right
return dummy.next
# 时间复杂度: O(n log n)
# 空间复杂度: O(log n)递归栈空间
4.5 LeetCode 493. 翻转对（困难）
题目描述： 给定一个数组 nums，如果 i < j 且 nums[i] > 2*nums[j]，则称 (i, j) 为一个重要翻转对。返回给定数组中的重要翻转对的数量。
解题思路： 在归并排序的过程中统计翻转对数量。
def reversePairs(nums: list[int]) -> int:
"""
统计翻转对数量
"""
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_count = merge_sort(arr[:mid])
right, right_count = merge_sort(arr[mid:])
# 统计跨越左右两部分的翻转对
cross_count = 0
j = 0
for i in range(len(left)):
while j < len(right) and left[i] > 2 * right[j]:
j += 1
cross_count += j
# 合并
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, left_count + right_count + cross_count
_, count = merge_sort(nums)
return count
# 测试
print(reversePairs([1,3,2,3,1])) # 2
print(reversePairs([2,4,3,5,1])) # 3
# 时间复杂度: O(n log n)
# 空间复杂度: O(n)
第五节：堆排序
5.1 堆的基本概念
堆是一种特殊的完全二叉树，分为最大堆和最小堆：
- 最大堆：每个节点的值都大于等于其子节点的值
- 最小堆：每个节点的值都小于等于其子节点的值
数组表示堆：
- 父节点索引：
(i - 1) // 2 - 左子节点索引：
2 * i + 1 - 右子节点索引：
2 * i + 2
5.2 堆排序实现
def heapSort(arr: list[int]) -> list[int]:
"""
堆排序
"""
def heapify(arr, n, i):
"""
调整堆，使以i为根的子树满足最大堆性质
n: 堆的大小
i: 当前节点索引
"""
largest = i
left = 2 * i + 1
right = 2 * i + 2
# 找到最大值的索引
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值不是根节点，交换并继续调整
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
n = len(arr)
# 构建最大堆（从最后一个非叶子节点开始）
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 一个个取出堆顶元素
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 交换
heapify(arr, i, 0) # 调整剩余堆
return arr
# 测试
print(heapSort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]
# 时间复杂度: O(n log n)
# 空间复杂度: O(1)
Go语言实现：
func heapSort(arr []int) []int {
heapify := func(arr []int, n, i int) {
largest := i
left := 2*i + 1
right := 2*i + 2
if left < n && arr[left] > arr[largest] {
largest = left
}
if right < n && arr[right] > arr[largest] {
largest = right
}
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
n := len(arr)
// 构建最大堆
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
// 排序
for i := n - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
}
return arr
}
5.3 LeetCode 347. 前 K 个高频元素（中等）
题目描述： 给定一个整数数组 nums 和一个整数 k，返回出现频率前 k 高的元素。
解题思路： 使用最小堆维护频率最高的k个元素。
import heapq
from collections import Counter
def topKFrequent(nums: list[int], k: int) -> list[int]:
"""
查找前k个高频元素
"""
# 统计频率
count = Counter(nums)
# 使用最小堆维护前k个高频元素
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for freq, num in heap]
# 测试
print(topKFrequent([1,1,1,2,2,3], 2)) # [1, 2]
print(topKFrequent([1], 1)) # [1]
# 时间复杂度: O(n log k)
# 空间复杂度: O(n)
方法二：使用快速选择（更优解）
def topKFrequent(nums: list[int], k: int) -> list[int]:
"""
使用快速选择算法
"""
count = Counter(nums)
unique = list(count.keys())
def partition(left, right):
pivot_freq = count[unique[right]]
i = left
for j in range(left, right):
if count[unique[j]] < pivot_freq:
unique[i], unique[j] = unique[j], unique[i]
i += 1
unique[i], unique[right] = unique[right], unique[i]
return i
def quickselect(left, right, k_smallest):
if left == right:
return
pivot_index = partition(left, right)
if k_smallest == pivot_index:
return
elif k_smallest < pivot_index:
quickselect(left, pivot_index - 1, k_smallest)
else:
quickselect(pivot_index + 1, right, k_smallest)
n = len(unique)
quickselect(0, n - 1, n - k)
return unique[n - k:]
# 时间复杂度: O(n)平均情况
# 空间复杂度: O(n)
5.4 LeetCode 295. 数据流的中位数（困难）
题目描述： 中位数是有序列表中间的数。设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
解题思路： 使用两个堆：最大堆存储较小的一半，最小堆存储较大的一半。
import heapq
class MedianFinder:
"""
数据流中位数查找器
"""
def __init__(self):
# 最大堆（存储较小的一半）
self.small = []
# 最小堆（存储较大的一半）
self.large = []
def addNum(self, num: int) -> None:
# 先加入最大堆
heapq.heappush(self.small, -num)
# 将最大堆的最大元素移到最小堆
heapq.heappush(self.large, -heapq.heappop(self.small))
# 平衡两个堆的大小
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2.0
# 测试
mf = MedianFinder()
mf.addNum(1)
mf.addNum(2)
print(mf.findMedian()) # 1.5
mf.addNum(3)
print(mf.findMedian()) # 2.0
# addNum时间复杂度: O(log n)
# findMedian时间复杂度: O(1)
# 空间复杂度: O(n)
第六节：其他经典排序题目
6.1 LeetCode 912. 排序数组（中等）
题目描述： 给定一个整数数组 nums，将该数组升序排列。
解题思路： 可以使用快速排序、归并排序或堆排序。这里展示随机化快排。
import random
def sortArray(nums: list[int]) -> list[int]:
"""
随机化快速排序
"""
def partition(left, right):
# 随机选择pivot
pivot_idx = random.randint(left, right)
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
pivot = nums[right]
i = left
for j in range(left, right):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[right] = nums[right], nums[i]
return i
def quicksort(left, right):
if left < right:
pi = partition(left, right)
quicksort(left, pi - 1)
quicksort(pi + 1, right)
quicksort(0, len(nums) - 1)
return nums
# 时间复杂度: O(n log n)平均
# 空间复杂度: O(log n)
6.2 LeetCode 75. 颜色分类（中等）
题目描述： 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。用整数 0、1 和 2 分别表示红色、白色和蓝色。
解题思路： 使用三路快排的思想，维护三个区域。
def sortColors(nums: list[int]) -> None:
"""
荷兰国旗问题
"""
p0 = 0 # [0, p0)区域全是0
p2 = len(nums) - 1 # (p2, len-1]区域全是2
curr = 0
while curr <= p2:
if nums[curr] == 0:
nums[p0], nums[curr] = nums[curr], nums[p0]
p0 += 1
curr += 1
elif nums[curr] == 2:
nums[curr], nums[p2] = nums[p2], nums[curr]
p2 -= 1
# curr不移动，因为交换来的元素还未检查
else:
curr += 1
# 测试
nums = [2,0,2,1,1,0]
sortColors(nums)
print(nums) # [0, 0, 1, 1, 2, 2]
# 时间复杂度: O(n)
# 空间复杂度: O(1)
6.3 LeetCode 179. 最大数（中等）
题目描述： 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
解题思路： 自定义比较函数，比较 x+y 和 y+x 的大小。
from functools import cmp_to_key
def largestNumber(nums: list[int]) -> str:
"""
组成最大数
"""
# 转换为字符串
nums_str = list(map(str, nums))
# 自定义比较函数
def compare(x, y):
if x + y > y + x:
return -1
elif x + y < y + x:
return 1
else:
return 0
# 排序
nums_str.sort(key=cmp_to_key(compare))
# 拼接结果
result = ''.join(nums_str)
# 处理全0的情况
return '0' if result[0] == '0' else result
# 测试
print(largestNumber([10,2])) # "210"
print(largestNumber([3,30,34,5,9])) # "9534330"
# 时间复杂度: O(n log n)
# 空间复杂度: O(n)
本章总结
本章详细讲解了二分查找和排序算法的核心知识：
二分查找要点：
- 掌握4种基本模板：精确查找、左边界、右边界、实数二分
- 理解二分查找的本质是在单调空间中寻找边界
- 注意边界条件的处理和循环不变量
- 灵活应用于旋转数组、峰值查找、速度二分等场景
排序算法要点：
快速排序：平均O(n log n)，原地排序，不稳定
- 三路快排优化处理重复元素
- 随机化避免最坏情况
- 快速选择算法求第K大元素
归并排序：O(n log n)，稳定排序，需要额外空间
- 适合链表排序
- 可用于统计逆序对等问题
堆排序：O(n log n)，原地排序，不稳定
- 堆的应用：TopK问题、中位数查找
- 优先队列的底层实现
复杂度对比：
| 算法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
下一章讲解树与递归算法，包括二叉树遍历、DFS、BFS和回溯算法。