Redian新闻
>
急问什么信用卡的点数可以转国内南航的里程? (转载)
avatar
急问什么信用卡的点数可以转国内南航的里程? (转载)# Money - 海外理财
s*r
1
大家有什么思路么?
How would you define a data structure that stores a set of values (i.e., a
value cannot appear more than one time), and implements the following
functions:
add(p)--adds the value p to the set
delete(p)--removes the value p from the set
getrandom()--returns a random value from the set (all items should be
equally likely). (Assume you have access to some nice random() function.)
avatar
d*5
2
【 以下文字转载自 Travel 讨论区 】
发信人: daydayup815 (david), 信区: Travel
标 题: 急问什么信用卡的点数可以转国内南航的里程?
发信站: BBS 未名空间站 (Thu Jun 12 12:00:39 2014, 美东)
必须得求得6万南航点数来换一张新航线的机票
不想用SPG换,1:1貌似非常不值(换完价值跟直接买也差不多了)
求教,谢谢!!
avatar
j*y
3
red-black tree/order statistics tree 可以吗?

【在 s****r 的大作中提到】
: 大家有什么思路么?
: How would you define a data structure that stores a set of values (i.e., a
: value cannot appear more than one time), and implements the following
: functions:
: add(p)--adds the value p to the set
: delete(p)--removes the value p from the set
: getrandom()--returns a random value from the set (all items should be
: equally likely). (Assume you have access to some nice random() function.)

avatar
H*U
4
淘宝
avatar
t*h
5
why not hashset directly

【在 s****r 的大作中提到】
: 大家有什么思路么?
: How would you define a data structure that stores a set of values (i.e., a
: value cannot appear more than one time), and implements the following
: functions:
: add(p)--adds the value p to the set
: delete(p)--removes the value p from the set
: getrandom()--returns a random value from the set (all items should be
: equally likely). (Assume you have access to some nice random() function.)

avatar
h*s
6
招商银行南航明珠卡。

【在 d*********5 的大作中提到】
: 【 以下文字转载自 Travel 讨论区 】
: 发信人: daydayup815 (david), 信区: Travel
: 标 题: 急问什么信用卡的点数可以转国内南航的里程?
: 发信站: BBS 未名空间站 (Thu Jun 12 12:00:39 2014, 美东)
: 必须得求得6万南航点数来换一张新航线的机票
: 不想用SPG换,1:1貌似非常不值(换完价值跟直接买也差不多了)
: 求教,谢谢!!

avatar
s*r
7
then how to do random output ?

【在 t*********h 的大作中提到】
: why not hashset directly
avatar
b*t
8
linkedhashset?

【在 t*********h 的大作中提到】
: why not hashset directly
avatar
p*2
9
等我做一下。
avatar
f*7
10
BST可以嘛?
add,delete就是常规操作
getRandom,就用蓄水池抽样,inorder一次
avatar
f*e
11
怎么感觉见过很多遍的样子。

【在 s****r 的大作中提到】
: 大家有什么思路么?
: How would you define a data structure that stores a set of values (i.e., a
: value cannot appear more than one time), and implements the following
: functions:
: add(p)--adds the value p to the set
: delete(p)--removes the value p from the set
: getrandom()--returns a random value from the set (all items should be
: equally likely). (Assume you have access to some nice random() function.)

avatar
t*h
15
i mean implement it like hashset by using a hashmap. since you have access
to buckets, its trivial to return a random item

【在 s****r 的大作中提到】
: then how to do random output ?
avatar
p*2
16

getrandom的复杂度应该是O(1)的,虽然LZ忘记说明了。

【在 t*********h 的大作中提到】
: i mean implement it like hashset by using a hashmap. since you have access
: to buckets, its trivial to return a random item

avatar
w*y
17
面过。
Array + hash map
Map 中key是p, value 是数组index.
Delete的时候稍微tricky点。
所有操作o(1)
avatar
h*o
18
yes

【在 b******t 的大作中提到】
: linkedhashset?
avatar
O*i
19
思路是不是这样?
首先想到用数组
取随机,O(1)得到随机的下标
插入,总在尾部,也就是STL vector的push_back, O(1),如果剩余空间足够大
删除,分两步。
第一步是查找,正常情况下要O(n)的从头开始依次找到位置,所以要配合一个hash表,
O(1)直接得到位置。这个类似hash + DLL实现LRU cache的思路
第二步是删除,正常情况下要O(n)移动所有后续元素向前一步来填补删除后的gap。但
是,参考用无序数组实现优先队列的trick: DelMin()找到最小的也就是优先级最高的
那个元素,删除它然后返回该元素的值。但删除操作无须移动元素,只要把最后一个元
素和它交换,然后数组大小shrink 1。

【在 p*****2 的大作中提到】
: http://blog.sina.com.cn/s/blog_b9285de20101gwnn.html
: 刚写了一个,放在了博客上边。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。