Meta 第K大：0/1起始排名与三路Quickselect

题目重点：核对第K大和索引K的区别，用三路随机选择处理重复值，并证明期望复杂度。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

重复值按排序位置计数，不去重。默认K为1起始，zero_based=True表示0起始索引；必须在写代码前确认。输入被复制，原数组保持不变。

解题路线

把降序rank转换成升序target=n−1−rank。普通第2大rank1，0起始位置2则rank2，这是不同接口而非算法争论。
随机pivot，用Dutch flag分成< pivot、= pivot、> pivot三段；scan遇小值换到small并同时前移，遇大值换到large只移动large，因为换来的元素还未分类。
target在等值段直接返回pivot；在左或右只继续相应子区间。所有元素相同一次分区结束，避免双路实现对重复值退化成每轮只减1。
随机pivot每次有常数概率落在中间一半，从而下一有效区间最多3/4大小；按几何缩小层次计算，每层期望常数次尝试，总扫描期望O(n)。这不是每次都均分保证，最坏仍O(n²)。
若需要确定性最坏线性，可以median-of-medians选枢轴；实现复杂度更高。小K的minheap基线O(n log K)也合法，除非题目明确要期望线性。

手动走一遍

[1,2,3,4,5,6,7,8]，默认K=2返回7；zero_based=True且K=2返回6。[5,5,4]第2大是5，不是4，因为本合同不按distinct rank。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

import random


def kth_largest(values,k,zero_based=False,rng=None):
    """Counts duplicate positions. Copies input; randomized 3-way quickselect."""
    rank=k if zero_based else k-1
    if not 0<=rank<len(values):raise ValueError('rank outside input')
    data=list(values);target=len(data)-1-rank
    rng=rng or random.Random();left=0;right=len(data)-1
    while left<=right:
        pivot=data[rng.randrange(left,right+1)]
        small=left;scan=left;large=right
        while scan<=large:
            if data[scan]<pivot:
                data[small],data[scan]=data[scan],data[small];small+=1;scan+=1
            elif data[scan]>pivot:
                data[scan],data[large]=data[large],data[scan];large-=1
            else:scan+=1
        if target<small:right=small-1
        elif target>large:left=large+1
        else:return pivot
    raise AssertionError('unreachable valid rank')

复杂度

随机选择期望O(n)、最坏O(n²)时间；算法迭代分区辅助O(1)，但本实现复制数组实际额外O(n)空间。若允许原地修改可省拷贝，不能忽略这个已发生的成本。

易错点与追问

容易失分的边界

把“第2大”默认为0起始却不告知调用者，会产生看似off-by-one争议。
等值pivot只处理一项导致重复数据严重退化。

继续深挖

若要求第K个不同值，应在哪层去重并计空间？
如何测试随机算法？用独立排序oracle固定seed，并包括全等值和极端rank。