l*y
发帖数: 21010 | 1 一看答案，妈的不就是swap么，应该很容易想到啊
智商低真是不好办 |
l*****a
发帖数: 14598 | 2 挖坑封ID
【在 l*y 的大作中提到】
: 一看答案，妈的不就是swap么，应该很容易想到啊
: 智商低真是不好办
|
l*y
发帖数: 21010 | 3 谁挖坑了，我就是问问大家是不是都能自己想出来
【在 l*****a 的大作中提到】
: 挖坑封ID
|
c*****a
发帖数: 808 | |
l*y
发帖数: 21010 | 5 对啊
【在 c*****a 的大作中提到】
: a家的card oop啊...
|
l*y
发帖数: 21010 | 6 这些题你们都背过？哪儿有？
【在 c*****a 的大作中提到】
: a家的card oop啊...
|
c********t
发帖数: 5706 | 7 reservoir sampling? 没事，没做过真的很难想，俺就不会。
【在 l*y 的大作中提到】
: 一看答案，妈的不就是swap么，应该很容易想到啊
: 智商低真是不好办
|
h**6
发帖数: 4160 | |
f*******t
发帖数: 7549 | 9 O(NlogN)时间+O(N)空间算法：
void shuffleArray(int *array, int n) {
pair *random = new pair[n];
set used;
for (int i = 0; i < n; i++) {
int r;
do {
r = random(INT_MIN, INT_MAX);
} while (used.find(r) != used.end());
random[i] = make_pair(r, i);
}
sort(random, random + n);
for(int i = 0; i < n; i++)
array[i] = random[i].second;
} |
c********t
发帖数: 5706 | 10 怎么会这么复杂？
O(n) 不行吗？
http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******t 的大作中提到】
: O(NlogN)时间+O(N)空间算法：
: void shuffleArray(int *array, int n) {
: pair *random = new pair[n];
: set used;
: for (int i = 0; i < n; i++) {
: int r;
: do {
: r = random(INT_MIN, INT_MAX);
: } while (used.find(r) != used.end());
: random[i] = make_pair(r, i);
|
f*******t
发帖数: 7549 | 11 我当年面A的时候，虽然知道有O(n)算法，但实在想不起来。面试官就跟我说能不能想
出个比O(n)差但比O(n^2)好的算法，我想了办天写出这个，面试官表示从没见过这种解
法，很满意。
所以说很多时候背不直观的最优解不如自己想一个新奇的解法。
【在 c********t 的大作中提到】
: 怎么会这么复杂？
: O(n) 不行吗？
: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
