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
相关阅读
有人做过Bloomberg 的online assessment没有免费送最高$250 Amazon GC 任意消费一笔SPG 信用卡Can the first year student find a not related full time job?请问去招聘会的真正意义何在？极其复杂的身份问题H1B--F1--J1有人知道高盛办绿卡的政策吗？Staff这个title烦，我到底该找什么样的工作啊？IT公司真实薪水Process engr openning in bay areaDatabase software engineer position available immediately (Atlanta)一周连收3 offer， 求选择建议。TSC的OPT批到哪里了？Business Analyst/Project manager Openingjob opennings in a company in bay area申请的group leader发面试通知的时候变成了staff职位这个版基本上就是CS找工作版Palantir finance面试怎么样？求教关于去加拿大和英国的工作how to check a bin tree is balanced?
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。