logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
find, insert, delete, getRandom in O(1)
avatar
find, insert, delete, getRandom in O(1)# JobHunting - 待字闺中
G*A
1 楼
之前讨论过，不过找不到原帖了。请大家给点思路
考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
还要自己implement hash with collision resolution?
avatar
w*x
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;
};
没测
avatar
p*2
3 楼

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

【在 G****A 的大作中提到】
: 之前讨论过，不过找不到原帖了。请大家给点思路
: 考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
: 还要自己implement hash with collision resolution?
avatar
G*A
4 楼
谢谢。 目前看到的解法都默认不会有duplicate key.
avatar
m*k
5 楼
hash with collision resolution is still for diff keys, just that they have
same hashcode
avatar
G*A
6 楼
之前讨论过，不过找不到原帖了。请大家给点思路
考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
还要自己implement hash with collision resolution?
avatar
w*x
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;
};
没测
avatar
p*2
8 楼

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

【在 G****A 的大作中提到】
: 之前讨论过，不过找不到原帖了。请大家给点思路
: 考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
: 还要自己implement hash with collision resolution?
avatar
G*A
9 楼
谢谢。 目前看到的解法都默认不会有duplicate key.
avatar
m*k
10 楼
hash with collision resolution is still for diff keys, just that they have
same hashcode
avatar
h*p
11 楼
mark
相关阅读
做硬件相关的就是钱少。。。Negotiate是跟manager还是跟HR？包子谢请教如何电话商量packageerror of couting total line number in txt file on MSDOS跳槽怎么找reference? (转载)nlp nature language processing有啥好资料看看观察到湾区双码工趋势 (转载)推荐一本好书HGST这家公司怎么样。。。Bracket Computing 怎样?求指教: Test engineer这种职位前景如何?今天刚结束的onsite, 求这里祈福，谢谢请教一道算法题真心求助想转WEB后端需要学什么技能？怎么withraw job application明天google onsite, 再这里祈福。Job: Web Designer/Developer (Contractor)新人求教：雇主多久能申请下来办H1B和e verify的资格？好操作吗？请教一道g算法题contract offer和正式offer的选择现在进药厂做分析能拿多少银子
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。