问一道车辆归位的算法题# JobHunting - 待字闺中
m*n
1 楼
有一个停车场，车位都是事先分配好的，每辆车都应该按编号停车。但是目前停车场所
停车辆并没用按编号停车，而且只有一个空位，请问如何利用这一个空位把所有车辆归
位。
感觉有点象华容道问题，求解，谢谢！
停车辆并没用按编号停车，而且只有一个空位，请问如何利用这一个空位把所有车辆归
位。
感觉有点象华容道问题，求解，谢谢！
l*8
2 楼
constant space, in-place sort
use quick sort.
【在 m******n 的大作中提到】
: 有一个停车场，车位都是事先分配好的，每辆车都应该按编号停车。但是目前停车场所
: 停车辆并没用按编号停车，而且只有一个空位，请问如何利用这一个空位把所有车辆归
: 位。
: 感觉有点象华容道问题，求解，谢谢！
use quick sort.
【在 m******n 的大作中提到】
: 有一个停车场，车位都是事先分配好的，每辆车都应该按编号停车。但是目前停车场所
: 停车辆并没用按编号停车，而且只有一个空位，请问如何利用这一个空位把所有车辆归
: 位。
: 感觉有点象华容道问题，求解，谢谢！
l*h
3 楼
一针见血。
【在 l*********8 的大作中提到】
: constant space, in-place sort
: use quick sort.
【在 l*********8 的大作中提到】
: constant space, in-place sort
: use quick sort.
m*n
4 楼
谢谢！
K*g
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 的大作中提到】
: 有一个停车场，车位都是事先分配好的，每辆车都应该按编号停车。但是目前停车场所
: 停车辆并没用按编号停车，而且只有一个空位，请问如何利用这一个空位把所有车辆归
: 位。
: 感觉有点象华容道问题，求解，谢谢！
这里车位和车都是对应的，只要是空车位，可以把车移到正确的车位上，
而不需要跟其他车去比较，因此用常见的排序无法得出最优方案。
更好的方案如下：
因为有一个空位，所以必然有个车位是没有对应的车的。先将其选出作为特殊车位，
如果该车位有车，移开。
按车位顺序查看停的车是否配对，若不配对将车放在特殊空位，把配对的车移在空出
来的车位，再给新空出来的车位配对，循环至空位变成特殊车位。之后从刚开始不配对
的车位往后继续查看配对，直至所有车位配对。复杂度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
6 楼
赞！
【在 K*******g 的大作中提到】
: 面试的时候碰到这道题，答得不好，面试官提示了。
: 这里车位和车都是对应的，只要是空车位，可以把车移到正确的车位上，
: 而不需要跟其他车去比较，因此用常见的排序无法得出最优方案。
: 更好的方案如下：
: 因为有一个空位，所以必然有个车位是没有对应的车的。先将其选出作为特殊车位，
: 如果该车位有车，移开。
: 按车位顺序查看停的车是否配对，若不配对将车放在特殊空位，把配对的车移在空出
: 来的车位，再给新空出来的车位配对，循环至空位变成特殊车位。之后从刚开始不配对
: 的车位往后继续查看配对，直至所有车位配对。复杂度O(n)，这里只考虑移车的开销。
: 举个例子，车位编号1-5， 车编号1-4，起始状态
【在 K*******g 的大作中提到】
: 面试的时候碰到这道题，答得不好，面试官提示了。
: 这里车位和车都是对应的，只要是空车位，可以把车移到正确的车位上，
: 而不需要跟其他车去比较，因此用常见的排序无法得出最优方案。
: 更好的方案如下：
: 因为有一个空位，所以必然有个车位是没有对应的车的。先将其选出作为特殊车位，
: 如果该车位有车，移开。
: 按车位顺序查看停的车是否配对，若不配对将车放在特殊空位，把配对的车移在空出
: 来的车位，再给新空出来的车位配对，循环至空位变成特殊车位。之后从刚开始不配对
: 的车位往后继续查看配对，直至所有车位配对。复杂度O(n)，这里只考虑移车的开销。
: 举个例子，车位编号1-5， 车编号1-4，起始状态
f*r
7 楼
感谢很棒的答案，
不过在给新空出来的车位配对的时候，感觉需要从前往后寻找对应的车，这个貌似本身
需要O(N)复杂度，那么总体的复杂度似乎没法保证是O(N)?
请赐教！
【在 K*******g 的大作中提到】
: 面试的时候碰到这道题，答得不好，面试官提示了。
: 这里车位和车都是对应的，只要是空车位，可以把车移到正确的车位上，
: 而不需要跟其他车去比较，因此用常见的排序无法得出最优方案。
: 更好的方案如下：
: 因为有一个空位，所以必然有个车位是没有对应的车的。先将其选出作为特殊车位，
: 如果该车位有车，移开。
: 按车位顺序查看停的车是否配对，若不配对将车放在特殊空位，把配对的车移在空出
: 来的车位，再给新空出来的车位配对，循环至空位变成特殊车位。之后从刚开始不配对
: 的车位往后继续查看配对，直至所有车位配对。复杂度O(n)，这里只考虑移车的开销。
: 举个例子，车位编号1-5， 车编号1-4，起始状态
不过在给新空出来的车位配对的时候，感觉需要从前往后寻找对应的车，这个貌似本身
需要O(N)复杂度，那么总体的复杂度似乎没法保证是O(N)?
请赐教！
【在 K*******g 的大作中提到】
: 面试的时候碰到这道题，答得不好，面试官提示了。
: 这里车位和车都是对应的，只要是空车位，可以把车移到正确的车位上，
: 而不需要跟其他车去比较，因此用常见的排序无法得出最优方案。
: 更好的方案如下：
: 因为有一个空位，所以必然有个车位是没有对应的车的。先将其选出作为特殊车位，
: 如果该车位有车，移开。
: 按车位顺序查看停的车是否配对，若不配对将车放在特殊空位，把配对的车移在空出
: 来的车位，再给新空出来的车位配对，循环至空位变成特殊车位。之后从刚开始不配对
: 的车位往后继续查看配对，直至所有车位配对。复杂度O(n)，这里只考虑移车的开销。
: 举个例子，车位编号1-5， 车编号1-4，起始状态
K*g
8 楼
建个table存一下位置就可以了，查询O(1)而已
【在 f*******r 的大作中提到】
: 感谢很棒的答案，
: 不过在给新空出来的车位配对的时候，感觉需要从前往后寻找对应的车，这个貌似本身
: 需要O(N)复杂度，那么总体的复杂度似乎没法保证是O(N)?
: 请赐教！
【在 f*******r 的大作中提到】
: 感谢很棒的答案，
: 不过在给新空出来的车位配对的时候，感觉需要从前往后寻找对应的车，这个貌似本身
: 需要O(N)复杂度，那么总体的复杂度似乎没法保证是O(N)?
: 请赐教！
相关阅读
要更新中国护照了，照片大家是怎么搞定的？a轮的公司期权应该怎么换算？华为的事对海外民企管理层有风险啊美政府没钱了，美国机场员工要闹罢工感谢 Pinterest抓孟晚舟后，很多公司要裁人破产。中资背景还可明明学了热门专业，毕业却觉得自己凉了第一个onsite: Indeed product scientist吐槽一下VmwareAmazon search team这么牛？GF 轮流为二流公司了?【工作机会】加州Verification Engineer (转载)不清楚自己为什么要读研读博，现在放弃也许还来得及工作4年及以上的人每天/每周/每月花多少时间在学习上？老印的宣传比老中厉害太多了请问Juniper network 现在情况怎样？亚麻assessment的难度如果接了offer可否反悔六零后即将退休，退休后如果无事做会无聊的转行但是没有h1b求教