m******n
发帖数: 42 | 1 有一个停车场，车位都是事先分配好的，每辆车都应该按编号停车。但是目前停车场所
停车辆并没用按编号停车，而且只有一个空位，请问如何利用这一个空位把所有车辆归
位。
感觉有点象华容道问题，求解，谢谢！ |
l*********8
发帖数: 4642 | 2 constant space, in-place sort
use quick sort.
【在 m******n 的大作中提到】
: 有一个停车场，车位都是事先分配好的，每辆车都应该按编号停车。但是目前停车场所
: 停车辆并没用按编号停车，而且只有一个空位，请问如何利用这一个空位把所有车辆归
: 位。
: 感觉有点象华容道问题，求解，谢谢！
|
l****h
发帖数: 1189 | 3 一针见血。
【在 l*********8 的大作中提到】
: constant space, in-place sort
: use quick sort.
|
m******n
发帖数: 42 | |
K*******g
发帖数: 26 | 5 面试的时候碰到这道题，答得不好，面试官提示了。
这里车位和车都是对应的，只要是空车位，可以把车移到正确的车位上，
而不需要跟其他车去比较，因此用常见的排序无法得出最优方案。
更好的方案如下：
因为有一个空位，所以必然有个车位是没有对应的车的。先将其选出作为特殊车位，
如果该车位有车，移开。
按车位顺序查看停的车是否配对，若不配对将车放在特殊空位，把配对的车移在空出
来的车位，再给新空出来的车位配对，循环至空位变成特殊车位。之后从刚开始不配对
的车位往后继续查看配对，直至所有车位配对。复杂度O(n)，这里只考虑移车的开销。
举个例子，车位编号1-5， 车编号1-4，起始状态
按车位顺序：
2， 3， 1， 4， 空
则移动如下
空， 3， 1， 4， 2
1， 3， 空，4， 2
1， 空， 3， 4， 2
1， 2， 3， 4， 空
结束
【在 m******n 的大作中提到】
: 有一个停车场，车位都是事先分配好的，每辆车都应该按编号停车。但是目前停车场所
: 停车辆并没用按编号停车，而且只有一个空位，请问如何利用这一个空位把所有车辆归
: 位。
: 感觉有点象华容道问题，求解，谢谢！
|
m******n
发帖数: 42 | 6 赞！
【在 K*******g 的大作中提到】
: 面试的时候碰到这道题，答得不好，面试官提示了。
: 这里车位和车都是对应的，只要是空车位，可以把车移到正确的车位上，
: 而不需要跟其他车去比较，因此用常见的排序无法得出最优方案。
: 更好的方案如下：
: 因为有一个空位，所以必然有个车位是没有对应的车的。先将其选出作为特殊车位，
: 如果该车位有车，移开。
: 按车位顺序查看停的车是否配对，若不配对将车放在特殊空位，把配对的车移在空出
: 来的车位，再给新空出来的车位配对，循环至空位变成特殊车位。之后从刚开始不配对
: 的车位往后继续查看配对，直至所有车位配对。复杂度O(n)，这里只考虑移车的开销。
: 举个例子，车位编号1-5， 车编号1-4，起始状态
|
f*******r
发帖数: 1086 | 7 感谢很棒的答案，
不过在给新空出来的车位配对的时候，感觉需要从前往后寻找对应的车，这个貌似本身
需要O(N)复杂度，那么总体的复杂度似乎没法保证是O(N)?
请赐教！
【在 K*******g 的大作中提到】
: 面试的时候碰到这道题，答得不好，面试官提示了。
: 这里车位和车都是对应的，只要是空车位，可以把车移到正确的车位上，
: 而不需要跟其他车去比较，因此用常见的排序无法得出最优方案。
: 更好的方案如下：
: 因为有一个空位，所以必然有个车位是没有对应的车的。先将其选出作为特殊车位，
: 如果该车位有车，移开。
: 按车位顺序查看停的车是否配对，若不配对将车放在特殊空位，把配对的车移在空出
: 来的车位，再给新空出来的车位配对，循环至空位变成特殊车位。之后从刚开始不配对
: 的车位往后继续查看配对，直至所有车位配对。复杂度O(n)，这里只考虑移车的开销。
: 举个例子，车位编号1-5， 车编号1-4，起始状态
|
K*******g
发帖数: 26 | 8 建个table存一下位置就可以了，查询O(1)而已
【在 f*******r 的大作中提到】
: 感谢很棒的答案，
: 不过在给新空出来的车位配对的时候，感觉需要从前往后寻找对应的车，这个貌似本身
: 需要O(N)复杂度，那么总体的复杂度似乎没法保证是O(N)?
: 请赐教！
|
