题目重点：重复值算独立位置，k从0开始。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 数值可排序，insert追加一个实例，findlargest(k)采用0based并越界拒绝。
- 不要求insert同时O(1)；query优先、Python数组给明确取舍。
解题路线
- 维护升序数组，用bisect定位插入位置后移动尾部元素。第k大直接values[n−1−k]，保留重复。
- 二分找位置O(logn)但list移位O(n)，因此不能说insert整体log。查询O(1)满足目标，代价是更新。
- 若insert也要log，用带子树size的平衡树，查询变log；固定k可维护topK小堆，但任意k不能直接索引heap的第k项，heap局部序不等全序。
手动走一遍
insert3/3/2，k0=3、k1=3、k2=2。k=n越界；重复去重会让k1错误得到2。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from bisect import insort
class Ranked:
def __init__(self):self.values=[]
def insert(self,num):insort(self.values,num)
def findlargest(self,k):
if not 0<=k<len(self.values):raise IndexError("zero-based rank")
return self.values[len(self.values)-1-k]
复杂度
insert O(n)时间，findlargest O(1)，空间O(n)；查询前k合法性O(1)。
易错点与追问
容易失分的边界
- 把bisect查找成本当全插入成本。
- 按heap数组index查询顺序统计量错误。
继续深挖
- 频繁批量insert后大量查询，怎样先排序再merge？
- 固定数值域时Fenwick频数查询第k大如何取舍？
