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