贡献一个一个L家的店面题目 - 未名空间MITBBS历史存档

g*e2015-10-28 07:10

1 楼

设计一个数据结构 add/remove/remove_rand 常数时间复杂度
follow up: 数据可重复
解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
调整数组的大小。
脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
才做出来，估计挂了。发出来赞个人品吧。
更正一下:
上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
用来支持remove_rand

q*c2015-10-28 07:10

2 楼

是不是用类似LRU的结构。

【在 g*******e 的大作中提到】

: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand

j*82015-10-28 07:10

3 楼

是必须要用数组吗？
不然的话double-linked list + hashmap就行了

【在 g*******e 的大作中提到】

: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand

g*e2015-10-28 07:10

4 楼

list怎么常数时间remove random?

【在 j*****8 的大作中提到】

: 是必须要用数组吗？
: 不然的话double-linked list + hashmap就行了

l*a2015-10-28 07:10

5 楼

你这个怎么做remove random

【在 j*****8 的大作中提到】

: 是必须要用数组吗？
: 不然的话double-linked list + hashmap就行了

j*82015-10-28 07:10

6 楼

用一个interger保存当前的size，然后生成一个random position remove就行
不过你说得对，需要另外一个map存。。

【在 l*****a 的大作中提到】

: 你这个怎么做remove random

g*e2015-10-28 07:10

7 楼

应该不是考察这个。

【在 q********c 的大作中提到】

: 是不是用类似LRU的结构。

g*e2015-10-28 07:10

8 楼

只有hash_map怎么在常数时间内定位一个随机键值?

【在 j*****8 的大作中提到】

: 用一个interger保存当前的size，然后生成一个random position remove就行
: 不过你说得对，需要另外一个map存。。

j*82015-10-28 07:10

9 楼

恩，又想了下，俺这个有问题
你说的那个数组的那个是对的！

【在 g*******e 的大作中提到】

: 只有hash_map怎么在常数时间内定位一个随机键值?

a*u2015-10-28 07:10

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*02015-10-28 07:10

11 楼

map存 ,就可以了吧。

【在 j*****8 的大作中提到】

: 用一个interger保存当前的size，然后生成一个random position remove就行
: 不过你说得对，需要另外一个map存。。

p*92015-10-28 07:10

12 楼

remove 和 remove_rand啥区别？

【在 g*******e 的大作中提到】

: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand

k*a2015-10-28 07:10

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*e2015-10-28 07:10

14 楼

设计一个数据结构 add/remove/remove_rand 常数时间复杂度
follow up: 数据可重复
解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
调整数组的大小。
脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
才做出来，估计挂了。发出来赞个人品吧。
更正一下:
上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
用来支持remove_rand

q*c2015-10-28 07:10

15 楼

是不是用类似LRU的结构。

【在 g*******e 的大作中提到】

: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand

j*82015-10-28 07:10

16 楼

是必须要用数组吗？
不然的话double-linked list + hashmap就行了

【在 g*******e 的大作中提到】

: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand

g*e2015-10-28 07:10

17 楼

list怎么常数时间remove random?

【在 j*****8 的大作中提到】

: 是必须要用数组吗？
: 不然的话double-linked list + hashmap就行了

l*a2015-10-28 07:10

18 楼

你这个怎么做remove random

【在 j*****8 的大作中提到】

: 是必须要用数组吗？
: 不然的话double-linked list + hashmap就行了

j*82015-10-28 07:10

19 楼

用一个interger保存当前的size，然后生成一个random position remove就行
不过你说得对，需要另外一个map存。。

【在 l*****a 的大作中提到】

: 你这个怎么做remove random

g*e2015-10-28 07:10

20 楼

应该不是考察这个。

【在 q********c 的大作中提到】

: 是不是用类似LRU的结构。

g*e2015-10-28 07:10

21 楼

只有hash_map怎么在常数时间内定位一个随机键值?

【在 j*****8 的大作中提到】

: 用一个interger保存当前的size，然后生成一个random position remove就行
: 不过你说得对，需要另外一个map存。。

j*82015-10-28 07:10

22 楼

恩，又想了下，俺这个有问题
你说的那个数组的那个是对的！

【在 g*******e 的大作中提到】

: 只有hash_map怎么在常数时间内定位一个随机键值?

a*u2015-10-28 07:10

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*02015-10-28 07:10

24 楼

map存 ,就可以了吧。

【在 j*****8 的大作中提到】

: 用一个interger保存当前的size，然后生成一个random position remove就行
: 不过你说得对，需要另外一个map存。。

p*92015-10-28 07:10

25 楼

remove 和 remove_rand啥区别？

【在 g*******e 的大作中提到】

: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand

k*a2015-10-28 07:10

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*02015-10-28 07:10

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*s2015-10-28 07:10

28 楼

remove不要真的删，而是放到一个“删除set“,即可。

【在 g*******e 的大作中提到】

: 设计一个数据结构 add/remove/remove_rand 常数时间复杂度
: follow up: 数据可重复
: 解题关键是常数时间删除数组内元素，就是把要删的挪到数组尾部然后
: 调整数组的大小。
: 脑袋不清楚，一直想着数组是有序的，找不到解题思路。在烙印的提示下
: 才做出来，估计挂了。发出来赞个人品吧。
: 更正一下:
: 上面说的不太清楚，除了数组之外，hash_map也是需要的。数组主要
: 用来支持remove_rand