Meta VO 面试真题解析：Multiset 实现与数组第 K 大元素

A multiset (also known as a bag) is a mutable, unordered collection of distinct objects that may appear more than once in the collection.

Implement a multiset that implements the following methods:

• add(element)
• remove(element)
• count(element)

Given an integer array and an integer k, return the kth largest element in the array.

Examples:

array = [5, -3, 9, 1]
k = 0 => return: 9
k = 1 => return: 5
k = 3 => return: -3

这道题考察两部分基础能力：一是用哈希表维护 multiset 中每个元素的出现次数，从而支持 add、remove 和 count 的高效操作；二是从整数数组中快速找到第 k 大元素。根据题面示例可知这里的 k 是从 0 开始计数，因此 k=0 对应最大值。常见做法是直接排序后取第 k 位，或者使用优先队列 / 快速选择在更高效的时间内完成查询；如果题目还要求多次增删查计数，则哈希表是核心数据结构。