g*******e
发帖数: 140 | 1 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
follow up: 数据可重复
解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
调整数组的大小。
脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
才做出来，估计挂了。发出来赞个人品吧。
更正一下:
上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
用来支持remove_rand |
q********c
发帖数: 1774 | 2 是不是用类似LRU的结构。
【在 g*******e 的大作中提到】
: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand
|
j*****8
发帖数: 3635 | 3 是必须要用数组吗？
不然的话double-linked list + hashmap就行了
【在 g*******e 的大作中提到】
: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand
|
g*******e
发帖数: 140 | 4 list怎么常数时间remove random?
【在 j*****8 的大作中提到】
: 是必须要用数组吗？
: 不然的话double-linked list + hashmap就行了
|
l*****a
发帖数: 14598 | 5 你这个怎么做remove random
【在 j*****8 的大作中提到】
: 是必须要用数组吗？
: 不然的话double-linked list + hashmap就行了
|
j*****8
发帖数: 3635 | 6 用一个interger保存当前的size，然后生成一个random position remove就行
不过你说得对，需要另外一个map存 。。
【在 l*****a 的大作中提到】
: 你这个怎么做remove random
|
g*******e
发帖数: 140 | 7 应该不是考察这个。
【在 q********c 的大作中提到】
: 是不是用类似LRU的结构。
|
g*******e
发帖数: 140 | 8 只有hash_map怎么在常数时间内定位一个随机键值?
【在 j*****8 的大作中提到】
: 用一个interger保存当前的size，然后生成一个random position remove就行
: 不过你说得对，需要另外一个map存 。。
|
j*****8
发帖数: 3635 | 9 恩，又想了下，俺这个有问题
你说的那个数组的那个是对的！
【在 g*******e 的大作中提到】
: 只有hash_map怎么在常数时间内定位一个随机键值?
|
a***u
发帖数: 383 | 10 import java.util.*;
public class DesignDataStructure {
Map> map = new HashMap>();
List list = new ArrayList();
public void add(int num){
list.add(num);
int index=list.size()-1;
if(map.containsKey(num)){
map.get(num).add(index);
}else{
Set set =new HashSet();
set.add(index);
map.put(num, set);
}
}
public void delete(int num){
if(map.containsKey(num)==false)
throw new RuntimeException("this number is not in the memory
");
Iterator it = map.get(num).iterator();
int index=it.next();
map.get(num).remove(index);
int last=list.get(list.size()-1);
list.set(index, last);
map.get(last).remove(list.size()-1);
map.get(last).add(index);
}
public void deletRandom(){
Random rand = new Random();
int index=rand.nextInt(list.size());
int num=list.get(index);
delete(num);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
} |
|
|
o******0
发帖数: 105 | 11
map存 ,就可以了吧。
【在 j*****8 的大作中提到】
: 用一个interger保存当前的size，然后生成一个random position remove就行
: 不过你说得对，需要另外一个map存 。。
|
p**********9
发帖数: 54 | 12 remove 和 remove_rand啥区别？
【在 g*******e 的大作中提到】
: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand
|
k******a
发帖数: 44 | 13 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后调整数组的大小。
这个方法虽然对remove_rand可行，但是如果做正常的remove， 那么这个数组如何维护？
看样子需要三个东西？
1. HashMap， （value -> count)
2. Array, (index -> value)
3. HashMap (value -> index)
Add操作： #1HashMap add, Array加入数组尾部，更新#3 hashmap
Remove操作： #1HashMap remove, 从#3 HashMap找到index， 然后remove value， 然
后在Array中根据index找到元素，和Array最后一个元素交换, 并更新数组size
Remove-Rand操作： 从array中随机选取第i个元素，得到value, 根据value，分别在#1
HashMap, #3 HashMap中remove。
重复元素在#1 HashMap中利用count处理，在#3 HashMap中利用list处理 （这里有些不
理想）。 |
g*******e
发帖数: 140 | 14 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
follow up: 数据可重复
解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
调整数组的大小。
脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
才做出来，估计挂了。发出来赞个人品吧。
更正一下:
上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
用来支持remove_rand |
q********c
发帖数: 1774 | 15 是不是用类似LRU的结构。
【在 g*******e 的大作中提到】
: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand
|
j*****8
发帖数: 3635 | 16 是必须要用数组吗？
不然的话double-linked list + hashmap就行了
【在 g*******e 的大作中提到】
: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand
|
g*******e
发帖数: 140 | 17 list怎么常数时间remove random?
【在 j*****8 的大作中提到】
: 是必须要用数组吗？
: 不然的话double-linked list + hashmap就行了
|
l*****a
发帖数: 14598 | 18 你这个怎么做remove random
【在 j*****8 的大作中提到】
: 是必须要用数组吗？
: 不然的话double-linked list + hashmap就行了
|
j*****8
发帖数: 3635 | 19 用一个interger保存当前的size，然后生成一个random position remove就行
不过你说得对，需要另外一个map存 。。
【在 l*****a 的大作中提到】
: 你这个怎么做remove random
|
g*******e
发帖数: 140 | 20 应该不是考察这个。
【在 q********c 的大作中提到】
: 是不是用类似LRU的结构。
|
|
|
g*******e
发帖数: 140 | 21 只有hash_map怎么在常数时间内定位一个随机键值?
【在 j*****8 的大作中提到】
: 用一个interger保存当前的size，然后生成一个random position remove就行
: 不过你说得对，需要另外一个map存 。。
|
j*****8
发帖数: 3635 | 22 恩，又想了下，俺这个有问题
你说的那个数组的那个是对的！
【在 g*******e 的大作中提到】
: 只有hash_map怎么在常数时间内定位一个随机键值?
|
a***u
发帖数: 383 | 23 import java.util.*;
public class DesignDataStructure {
Map> map = new HashMap>();
List list = new ArrayList();
public void add(int num){
list.add(num);
int index=list.size()-1;
if(map.containsKey(num)){
map.get(num).add(index);
}else{
Set set =new HashSet();
set.add(index);
map.put(num, set);
}
}
public void delete(int num){
if(map.containsKey(num)==false)
throw new RuntimeException("this number is not in the memory
");
Iterator it = map.get(num).iterator();
int index=it.next();
map.get(num).remove(index);
if(map.get(num).isEmpty())
map.remove(num);
int last=list.get(list.size()-1);
list.set(index, last);
map.get(last).remove(list.size()-1);
map.get(last).add(index);
}
public void deletRandom(){
Random rand = new Random();
int index=rand.nextInt(list.size());
int num=list.get(index);
delete(num);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
} |
o******0
发帖数: 105 | 24
map存 ,就可以了吧。
【在 j*****8 的大作中提到】
: 用一个interger保存当前的size，然后生成一个random position remove就行
: 不过你说得对，需要另外一个map存 。。
|
p**********9
发帖数: 54 | 25 remove 和 remove_rand啥区别？
【在 g*******e 的大作中提到】
: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand
|
k******a
发帖数: 44 | 26 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后调整数组的大小。
这个方法虽然对remove_rand可行，但是如果做正常的remove， 那么这个数组如何维护？
看样子需要三个东西？
1. HashMap， （value -> count)
2. Array, (index -> value)
3. HashMap (value -> index)
Add操作： #1HashMap add, Array加入数组尾部，更新#3 hashmap
Remove操作： #1HashMap remove, 从#3 HashMap找到index， 然后remove value， 然
后在Array中根据index找到元素，和Array最后一个元素交换, 并更新数组size
Remove-Rand操作： 从array中随机选取第i个元素，得到value, 根据value，分别在#1
HashMap, #3 HashMap中remove。
重复元素在#1 HashMap中利用count处理，在#3 HashMap中利用list处理 （这里有些不
理想）。 |
h********0
发帖数: 74 | 27 remove-rand by index ? or remove-rand by value?
example:
input {1, 2, 1},
if remove-rand by index, three nums have the same possibility to be
removed
if remove-rand by value, two distinct nums have the same possibility to
be removed.
小。
护？
#1
【在 k******a 的大作中提到】
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后调整数组的大小。
: 这个方法虽然对remove_rand可行，但是如果做正常的remove， 那么这个数组如何维护？
: 看样子需要三个东西？
: 1. HashMap， （value -> count)
: 2. Array, (index -> value)
: 3. HashMap (value -> index)
: Add操作： #1HashMap add, Array加入数组尾部，更新#3 hashmap
: Remove操作： #1HashMap remove, 从#3 HashMap找到index， 然后remove value， 然
: 后在Array中根据index找到元素，和Array最后一个元素交换, 并更新数组size
: Remove-Rand操作： 从array中随机选取第i个元素，得到value, 根据value，分别在#1
|
l******s
发帖数: 3045 | 28 remove不要真的删，而是放到一个“删除set“,即可。
【在 g*******e 的大作中提到】
: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand
|
