e***s
发帖数: 799 | 1 做一个负载平衡器的类，构造函数输入N，就初始化N个空闲的服务器，实现三个方法，
1.标记一个服务器为繁忙服务器；2.释放一个繁忙服务器；3.随机找一个空闲服务器， |
f*******t
发帖数: 7549 | |
e***s
发帖数: 799 | 3 这题理论上跟，“设计一个数据结构，add(p), delete(p), findRandom(), 都用O(1)
”是一道题，但是他没说要求O(1)，只是要我做完后分析复杂度。
最后反正就是ArrayList + HashTable
【在 f*******t 的大作中提到】
: bless。数据结构怎么选？
|
p*****2
发帖数: 21240 | 4 数组就行了吧 n使固定的
【在 e***s 的大作中提到】
: 这题理论上跟，“设计一个数据结构，add(p), delete(p), findRandom(), 都用O(1)
: ”是一道题，但是他没说要求O(1)，只是要我做完后分析复杂度。
: 最后反正就是ArrayList + HashTable
|
f*******t
发帖数: 7549 | 5 是的，我也想到这题了，但一时想不起来怎么做
【在 e***s 的大作中提到】
: 这题理论上跟，“设计一个数据结构，add(p), delete(p), findRandom(), 都用O(1)
: ”是一道题，但是他没说要求O(1)，只是要我做完后分析复杂度。
: 最后反正就是ArrayList + HashTable
|
e***s
发帖数: 799 | 6 二爷，我也一开始也是数组，但是但一个数组怎么样使findRandom() O(1)呢？
【在 p*****2 的大作中提到】
: 数组就行了吧 n使固定的
|
x*******6
发帖数: 262 | 7 这个跟设计一个类，支持add delete getRandom时间复杂度为O(1)是一个套路吧，用一
个hashmap和一个array |
p*****2
发帖数: 21240 | 8
数组和ArrayList有啥区别呀？对于这道题来说？
【在 e***s 的大作中提到】
: 二爷，我也一开始也是数组，但是但一个数组怎么样使findRandom() O(1)呢？
|
j******2
发帖数: 362 | 9 能否再提示下hashmap怎么支持constant time random()?
【在 x*******6 的大作中提到】
: 这个跟设计一个类，支持add delete getRandom时间复杂度为O(1)是一个套路吧，用一
: 个hashmap和一个array
|
j******2
发帖数: 362 | |
|
|
p*****2
发帖数: 21240 | 11
看看我的博客吧。
http://blog.sina.com.cn/s/blog_b9285de20101gx01.html
【在 j******2 的大作中提到】
: 能否再提示下hashmap怎么支持constant time random()?
|
c********t
发帖数: 5706 | 12 有区别，数组固定长度，删除要重新初始化一个新的数组
这题要用ArrayList，删除尾巴吧
【在 p*****2 的大作中提到】
:
: 看看我的博客吧。
: http://blog.sina.com.cn/s/blog_b9285de20101gx01.html
|
p*****2
发帖数: 21240 | 13
为什么一定要删除？
【在 c********t 的大作中提到】
: 有区别，数组固定长度，删除要重新初始化一个新的数组
: 这题要用ArrayList，删除尾巴吧
|
f*******t
发帖数: 7549 | 14 看你代码后想起来了。要是面试时碰到这种本来会做的题却怎么都想不起最优解，那真
是悲催
【在 p*****2 的大作中提到】
:
: 为什么一定要删除？
|
j*****y
发帖数: 1071 | 15 感觉可以用长度为 N的一个array
用一个 index mid 来 表示 mid 左边是繁忙的，mid右边是空闲的，
比如 N = 5, mid = 2, 那么 A[0], A[1], A[2] 是繁忙的， A[3], A[4]是空闲的.
下面用 hashmap 来记录 某个 服务器 j 所在的 index i: hashmap(j) = i;
标记服务器j为 繁忙服务器, 先 check hashmap(j) 是否 <= mid, 是的话，表明
j 是繁忙的， 不用做什么。 否则， j 是空闲的，
int x = hashmap(j);
swap(A[mid + 1], A[x]);
hashmap(A[x]) = x;
hashmap(j) = mid + 1
mid ++;
释放一个繁忙的服务器方法类似
随机返回一个空闲的服务器。
int x = random(mid + 1, N -1);
return A[x];
【在 e***s 的大作中提到】
: 做一个负载平衡器的类，构造函数输入N，就初始化N个空闲的服务器，实现三个方法，
: 1.标记一个服务器为繁忙服务器；2.释放一个繁忙服务器；3.随机找一个空闲服务器，
|
j*****y
发帖数: 1071 | 16 而且这个hashmap用 direct access table实现就行了
【在 j*****y 的大作中提到】
: 感觉可以用长度为 N的一个array
: 用一个 index mid 来 表示 mid 左边是繁忙的，mid右边是空闲的，
: 比如 N = 5, mid = 2, 那么 A[0], A[1], A[2] 是繁忙的， A[3], A[4]是空闲的.
: 下面用 hashmap 来记录 某个 服务器 j 所在的 index i: hashmap(j) = i;
: 标记服务器j为 繁忙服务器, 先 check hashmap(j) 是否 <= mid, 是的话，表明
: j 是繁忙的， 不用做什么。 否则， j 是空闲的，
: int x = hashmap(j);
: swap(A[mid + 1], A[x]);
: hashmap(A[x]) = x;
: hashmap(j) = mid + 1
|
r******k
发帖数: 46 | 17 这个方法才是这题的正解啊
【在 j*****y 的大作中提到】
: 感觉可以用长度为 N的一个array
: 用一个 index mid 来 表示 mid 左边是繁忙的，mid右边是空闲的，
: 比如 N = 5, mid = 2, 那么 A[0], A[1], A[2] 是繁忙的， A[3], A[4]是空闲的.
: 下面用 hashmap 来记录 某个 服务器 j 所在的 index i: hashmap(j) = i;
: 标记服务器j为 繁忙服务器, 先 check hashmap(j) 是否 <= mid, 是的话，表明
: j 是繁忙的， 不用做什么。 否则， j 是空闲的，
: int x = hashmap(j);
: swap(A[mid + 1], A[x]);
: hashmap(A[x]) = x;
: hashmap(j) = mid + 1
|
