dedecms制作的网站,网站主机教程,家乡ppt模板免费下载网站,ps软件下载网站题目 给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。 请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 一、代码实现#xff08;快速选择…题目 给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。 请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 一、代码实现快速选择算法
import (math/randtime
)func findKthLargest(nums []int, k int) int {rand.Seed(time.Now().UnixNano())return quickSelect(nums, 0, len(nums)-1, k)
}func quickSelect(nums []int, left, right, k int) int {if left right {return nums[left]}pivotIndex : rand.Intn(right-left1) leftpivotVal : nums[pivotIndex]// 三路分区low, mid, high : left, left, rightfor mid high {if nums[mid] pivotVal {nums[low], nums[mid] nums[mid], nums[low]lowmid} else if nums[mid] pivotVal {mid} else {nums[mid], nums[high] nums[high], nums[mid]high--}}leftLength : low - leftif k leftLength {return quickSelect(nums, left, low-1, k)}midLength : high - low 1if k leftLengthmidLength {return pivotVal}return quickSelect(nums, high1, right, k-(leftLengthmidLength))
}二、算法分析
1. 核心思路
快速选择算法基于快速排序的分治思想但每次仅递归处理包含目标的子数组。三路分区将数组划分为大于、等于、小于基准值的三部分减少不必要的递归。随机基准随机选择基准值避免最坏情况确保平均时间复杂度为O(n)。
2. 关键步骤
随机基准选择随机选取一个元素作为基准值pivotVal。三路分区操作 low指针左侧元素均大于pivotVal。mid遍历数组将元素分类到对应区域。high指针右侧元素均小于pivotVal。 递归决策 若左区长度≥k递归处理左区。若k在左区和中区总长内直接返回pivotVal。否则递归处理右区调整k值。
3. 复杂度
指标值说明时间复杂度O(n)平均情况每次处理规模减半空间复杂度O(log n)递归调用栈深度最坏O(n)随机化避免
三、图解示例 四、边界条件与扩展
1. 特殊场景验证
全相同元素如[3,3,3], k2直接返回3。k1或kn处理最大或最小元素。逆序/顺序数组随机基准确保效率。
2. 扩展应用
前k大元素修改返回逻辑收集元素。流式数据结合堆结构处理动态数据。多维数据定义合适比较规则处理复杂结构。
3. 多语言实现
import randomdef findKthLargest(nums, k):def quick_select(left, right, k):if left right:return nums[left]pivot_index random.randint(left, right)pivot_val nums[pivot_index]low, mid, high left, left, rightwhile mid high:if nums[mid] pivot_val:nums[low], nums[mid] nums[mid], nums[low]low 1mid 1elif nums[mid] pivot_val:mid 1else:nums[mid], nums[high] nums[high], nums[mid]high - 1if k low - left:return quick_select(left, low-1, k)elif k (low - left) (high - low 1):return pivot_valelse:return quick_select(high1, right, k - (low - left high - low 1))return quick_select(0, len(nums)-1, k)import java.util.Random;public class Solution {private static final Random rand new Random();public int findKthLargest(int[] nums, int k) {return quickSelect(nums, 0, nums.length - 1, k);}private int quickSelect(int[] nums, int left, int right, int k) {if (left right) return nums[left];int pivotIndex rand.nextInt(right - left 1) left;int pivotVal nums[pivotIndex];int low left, mid left, high right;while (mid high) {if (nums[mid] pivotVal) {swap(nums, low, mid);} else if (nums[mid] pivotVal) {mid;} else {swap(nums, mid, high--);}}int leftLen low - left;if (k leftLen) return quickSelect(nums, left, low - 1, k);int midLen high - low 1;if (k leftLen midLen) return pivotVal;return quickSelect(nums, high 1, right, k - (leftLen midLen));}private void swap(int[] nums, int i, int j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}
}五、总结与优化
1. 算法对比
方法优势适用场景快速选择平均O(n)大规模数据求Top k堆适合动态数据实时处理流数据排序后取数实现简单小规模数据
2. 工程优化
尾递归优化减少递归栈深度。迭代实现改用循环结构避免栈溢出。内存优化处理原数组避免额外空间。
3. 扩展方向
并行处理多线程加速分区过程。适应性优化根据数据分布自动选择策略。稳定性增强处理元素相等时的稳定性需求。
