- 正确答案：第k大的数，即在无序数组中找到排序后从大到小第k个位置的元素（k从1开始计数）。例如数组[3,2,1,5,6,4]，k=2时，排序后为[6,5,4,3,2,1]，第2大是5。 ✅ O(n log n)方法：直接排序后取索引n−k处元素（升序排列）或k−1处（降序排列）。 ✅ O(n)方法：使用快速选择算法（QuickSelect），是快排的分治剪枝版本，期望时间复杂度O(n)，最坏O(n²)，但通过随机化基准可规避最坏情况；也可用堆（但堆方法实际是O(n log k)，不满足严格O(n)，故此处O(n)仅指QuickSelect）。 - 解答思路： 1. 先明确“第k大”等价于“升序数组中索引为n−k的元素”（0-based），因此问题转化为寻找第(n−k+1)小的元素（即第t小，t = n−k+1）。 2. O(n log n)解法最直观：调用内置排序（如Timsort/Introsort），稳定可靠，适合面试快速切入。 3. O(n)解法需避免全量排序，利用分治思想——每次partition将数组划分为< pivot、= pivot、> pivot三部分，根据t与各段长度关系决定递归方向： - 若t落在左段（< pivot），则在左段递归找第t小； - 若t落在pivot段（即t ∈ [left_len+1, left_len+equal_len]），直接返回pivot； - 否则在右段递归找第(t − left_len − equal_len)小。这样每次舍弃约一半数据，期望比较次数为 n + n/2 + n/4 + ... ≈ 2n，故期望O(n)。 - 深度知识讲解：【底层原理】 QuickSelect的核心是Lomuto或Hoare分区方案。Lomuto更易理解（单指针扫描），Hoare更高效（双指针向中间收缩，交换次数更少）。Java/Python内置的nth_element（C++）或randomized_select（CLRS）均基于Hoare变体。【为什么期望O(n)？】假设每次pivot恰好将数组二分（理想情况），则递归式为 T(n) = T(n/2) + O(n) → 主定理得T(n)=O(n)。即使pivot选得较差（如1/10:9/10分割），只要分割比例有常数界（如α∈(0,0.5)），仍满足T(n) ≤ T(αn) + O(n)，解为O(n)。而随机选pivot使每次分割的期望比例为1/2，数学期望下总比较次数为≤ 4n（可严格证明）。【稳定性与原地性】 QuickSelect是原地算法（in-place），仅需O(log n)栈空间（递归深度期望log n）；不保证稳定性（因swap破坏相对顺序），但本题无需稳定。【对比其他O(n)候选】 - 中位数的中位数（Median of Medians）算法：严格最坏O(n)，但常数极大（≈ 24n比较），工程中几乎不用； - 堆方法：建大小为k的最小堆遍历数组，时间O(n log k)，当k=Θ(n)时退化为O(n log n)，不满足题目要求的O(n)；因此面试中推荐随机化QuickSelect作为O(n)标准解。【边界与鲁棒性】需校验k合法性（1 ≤ k ≤ n），并处理重复元素——分区必须严格划分为<、=、>三段（三路快排思想），否则重复pivot可能导致无限递归或逻辑错误。 - 代码示例（Python，含详细注释）： # O(n log n) 方法：简单直接，适合初筛或k接近n时 def find_kth_largest_nlogn(nums, k): if not nums or k < 1 or k > len(nums): raise ValueError("k out of range") nums_sorted = sorted(nums) # 升序 return nums_sorted[len(nums) - k] # 第k大 = 升序下标n-k # O(n) 方法：随机化快速选择（三路分区，防重复恶化） import random def find_kth_largest_on(nums, k): if not nums or k < 1 or k > len(nums): raise ValueError("k out of range") n = len(nums) # 转为找第t小元素（t从1开始） t = n - k + 1 # 闭区间递归函数：在nums[l:r+1]中找第t_small小的数（t_small从1开始） def quickselect(l, r, t_small): if l == r: return nums[l] # 随机选择pivot并移到末尾（避免有序数组最坏情况） pivot_idx = random.randint(l, r) nums[pivot_idx], nums[r] = nums[r], nums[pivot_idx] pivot_val = nums[r] # 三路分区：lt指向< pivot末尾，gt指向> pivot开头 lt = l - 1 # nums[l:lt+1] < pivot i = l # 扫描指针 gt = r + 1 # nums[gt:r+1] > pivot while i < gt: if nums[i] < pivot_val: lt += 1 nums[lt], nums[i] = nums[i], nums[lt] i += 1 elif nums[i] > pivot_val: gt -= 1 nums[i], nums[gt] = nums[gt], nums[i] # i不增，因为换来的nums[i]未检查 else: i += 1 # 现在区间划分： # [l, lt] → < pivot # [lt+1, gt-1] → == pivot # [gt, r] → > pivot left_len = lt - l + 1 mid_len = (gt - 1) - (lt + 1) + 1 # = gt - lt - 1 if t_small <= left_len: return quickselect(l, lt, t_small) elif t_small <= left_len + mid_len: return pivot_val else: # 在右段找第 (t_small - left_len - mid_len) 小 return quickselect(gt, r, t_small - left_len - mid_len) return quickselect(0, n - 1, t) # 测试用例 # print(find_kth_largest_on([3,2,1,5,6,4], 2)) # 输出5 # print(find_kth_largest_on([3,2,1,5,6,4], 1)) # 输出6 - 扩展知识： 1. 工程实践：C++ STL的std::nth_element即采用IntroSelect（introspective selection）：结合QuickSelect + Median-of-3 pivot + 切换到heapselect当递归深度超阈值，保证最坏O(n log n)但平均极快。 2. 分布式场景：若数组分布在多台机器上，可用“分布式QuickSelect”：先全局采样估算pivot范围，再按pivot广播过滤，减少网络传输。 3. 流式数据：若数据是数据流且内存受限，可用Reservoir Sampling + heap近似求第k大，但无法保证精确O(n)。 4. 相关变种：第k小、前k大（返回k个元素）、带权第k大（每个元素有权重，按累积权重找）等，均需调整partition逻辑。 - 面试提示： - 首先给出O(n log n)解展示代码能力与清晰逻辑； - 再主动提出可优化至O(n)，体现算法敏感度； - 解释时强调“期望O(n)”而非“保证O(n)”，并说明随机化的必要性； - 若被问及最坏情况，可补充：“可通过Median-of-Medians保证最坏O(n)，但常数过大，实际性能不如随机化”。 - 务必手写分区过程（尤其三路），面试官常考察边界处理能力。

京东外卖推荐算法实习一面 40min

全站热榜

创作者周榜