find, insert, delete, getRandom in O(1) - 未名空间MITBBS历史存档 | Redian News

国际科技财经博客移民网络热点娱乐民生时事公众号

>JobHunting - 待字闺中

>

find, insert, delete, getRandom in O(1)

find, insert, delete, getRandom in O(1)# JobHunting - 待字闺中

G*A2013-02-04 08:02

1 楼

之前讨论过，不过找不到原帖了。请大家给点思路
考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
还要自己implement hash with collision resolution?

w*x2013-02-04 08:02

2 楼

/*
Given a collection of integer, design a class that supports:
add(data) - insert an element
delete(data) - delete an element
getRandom(data) - return a random element
*/
class Solution
{
public:
void add(int x)
{
if (m_mp.find(x) != m_mp.end())
return;
m_vec.push_back(x);
m_mp[x] = m_vec.size()-1;
}
void del(int x)
{
if (m_mp.find(x) == m_mp.end())
return;
int index = m_mp[x];
m_mp.erase(m_mp.find(x));
if (index != m_vec.size()-1)
{
swap(m_vec[index], m_vec[m_vec.size()-1]);
m_mp[m_vec[index]] = index;
}
m_vec.pop_back();
}
int getRandom()
{
return m_vec[rand()%m_vec.size()];
}
private:
hash_map m_mp;
vector m_vec;
};
没测

p*22013-02-04 08:02

3 楼

http://blog.sina.com.cn/s/blog_b9285de20101gx01.html

【在 G****A 的大作中提到】

: 之前讨论过，不过找不到原帖了。请大家给点思路
: 考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
: 还要自己implement hash with collision resolution?

G*A2013-02-04 08:02

4 楼

谢谢。目前看到的解法都默认不会有duplicate key.

m*k2013-02-04 08:02

5 楼

hash with collision resolution is still for diff keys, just that they have
same hashcode

G*A2013-02-04 08:02

6 楼

之前讨论过，不过找不到原帖了。请大家给点思路
考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
还要自己implement hash with collision resolution?

w*x2013-02-04 08:02

7 楼

/*
Given a collection of integer, design a class that supports:
add(data) - insert an element
delete(data) - delete an element
getRandom(data) - return a random element
*/
class Solution
{
public:
void add(int x)
{
if (m_mp.find(x) != m_mp.end())
return;
m_vec.push_back(x);
m_mp[x] = m_vec.size()-1;
}
void del(int x)
{
if (m_mp.find(x) == m_mp.end())
return;
int index = m_mp[x];
m_mp.erase(m_mp.find(x));
if (index != m_vec.size()-1)
{
swap(m_vec[index], m_vec[m_vec.size()-1]);
m_mp[m_vec[index]] = index;
}
m_vec.pop_back();
}
int getRandom()
{
return m_vec[rand()%m_vec.size()];
}
private:
hash_map m_mp;
vector m_vec;
};
没测

p*22013-02-04 08:02

8 楼

http://blog.sina.com.cn/s/blog_b9285de20101gx01.html

【在 G****A 的大作中提到】

: 之前讨论过，不过找不到原帖了。请大家给点思路
: 考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
: 还要自己implement hash with collision resolution?

G*A2013-02-04 08:02

9 楼

谢谢。目前看到的解法都默认不会有duplicate key.

m*k2013-02-04 08:02

10 楼

hash with collision resolution is still for diff keys, just that they have
same hashcode

h*p2013-02-04 08:02

11 楼

mark

热点事件追踪

美国公司裁员Layoff

2024-01-28 18:01

2024-01-09 19:01

2024-01-07 18:01

美国堕胎权争议

2024-01-06 18:01

美国枪击案

2024-01-06 18:01

2023-12-13 17:12

2023-12-02 07:12

2023-11-26 18:11

中美航班重磅消息！每周85班，直飞更方便！

微软、亚马逊、谷歌大裁员！哪些科技和零售公司有缩减规模计划？

中国外长王毅：中美关系已经止跌回稳

脱轨事故造成20多人受伤联邦调查纽约市全部地铁系统

更多 2024-11-05 的新闻