j******2
发帖数: 362 | 1 请问这题的count(i)究竟咩意思？
二爷为何说这题跟O(1) add(), del(), rand() data structure 那题一样？恕愚钝。
难道是：用random产生0到size()间的整数i，然后遍历整个set，凡count(j)>count(
i)的，delete之并存之。然后delete(i)。最后把delete的其他数又insert进去。
感觉很不efficient但是题目不要求complexity的话也可以。 | l*****a
发帖数: 14598 | 2 把题目说清楚点,不要道听途说的题都拿出来
另外,数据结构相关题目提到random access,都是用数组index访问
跟概率无关
【在 j******2 的大作中提到】
: 请问这题的count(i)究竟咩意思？
: 二爷为何说这题跟O(1) add(), del(), rand() data structure 那题一样？恕愚钝。
: 难道是：用random产生0到size()间的整数i，然后遍历整个set，凡count(j)>count(
: i)的，delete之并存之。然后delete(i)。最后把delete的其他数又insert进去。
: 感觉很不efficient但是题目不要求complexity的话也可以。
| j******2
发帖数: 362 | 3 原题如下
Given a set, and functions insert(i), delete(i), count(i), size(), random.
Design a data structure and implement PopRandom() to pop a random element
from the set and return it. |
|
