b******i
发帖数: 914 | 1 find a intersection to build office so that the sum of all employees’
commute distances is minimum. （the map is represented as a m*n grid, you
are given each employee’s coordination, they can only move in up-down and
left-right directions）
这是Google一道面试题。我能想到的就是从每个employee做BFS，再求出非employee的
格子的最短路径之和。找个和最小的格子。请问这题还有更简单的方法吗？ |
k******4
发帖数: 94 | 2 分别找x，y方向的median，O(n)时间，O（1）空间。 |
a********m
发帖数: 15480 | 3 找median O(1)空间能搞定吗，在O(n)时间的前提下？
【在 k******4 的大作中提到】
: 分别找x，y方向的median，O(n)时间，O（1）空间。
|
b******i
发帖数: 914 | 4 Good point
我忘了，一维的情况为什么median是距离最短的？
这题还有个变种，matrix中有的格子是block，是否只能bfs了？
【在 k******4 的大作中提到】
: 分别找x，y方向的median，O(n)时间，O（1）空间。
|
a********m
发帖数: 15480 | 5 排序以后从最外往里面消去。只考虑最外两个人，对于他们的区别来说只有两种情况：
在两个人里面还是在两个人外面，如果在里面两个走的距离不可避免是他们之间的距离
；在外面的话会超过这个距离。所以选的点必定在他们之间。而且因为路径长度不变，
所以去掉不影响最后结果。重复这个过程。到最后如果只有一个人的时候类似，两种情
况变成在他家还是不在他家，不在的话肯定比在他家更远。如果最后剩两个人，任意一
个在这两人之间的点都没区别，包括这两个人的位置。
啥叫有的格子是block?
【在 b******i 的大作中提到】
: Good point
: 我忘了，一维的情况为什么median是距离最短的？
: 这题还有个变种，matrix中有的格子是block，是否只能bfs了？
|
i*******e
发帖数: 114 | 6
有的格子是障碍物吧
【在 a********m 的大作中提到】
: 排序以后从最外往里面消去。只考虑最外两个人，对于他们的区别来说只有两种情况：
: 在两个人里面还是在两个人外面，如果在里面两个走的距离不可避免是他们之间的距离
: ；在外面的话会超过这个距离。所以选的点必定在他们之间。而且因为路径长度不变，
: 所以去掉不影响最后结果。重复这个过程。到最后如果只有一个人的时候类似，两种情
: 况变成在他家还是不在他家，不在的话肯定比在他家更远。如果最后剩两个人，任意一
: 个在这两人之间的点都没区别，包括这两个人的位置。
: 啥叫有的格子是block?
|
a********m
发帖数: 15480 | 7 哦。那比较烦了。感觉用dp比较好。每个人单独算一遍，最后整个map扫描一遍。
修改一下，bfs应该可以，dp没好处。
【在 i*******e 的大作中提到】
:
: 有的格子是障碍物吧
|
k******4
发帖数: 94 | 8 基于qiuck select的方法找median可以吧，不用递归而是循环。
【在 a********m 的大作中提到】
: 找median O(1)空间能搞定吗，在O(n)时间的前提下？
|
a********m
发帖数: 15480 | 9 看了一下，你说的对，in place可以constant memory overhead。
【在 k******4 的大作中提到】
: 基于qiuck select的方法找median可以吧，不用递归而是循环。
|
S********s
发帖数: 29 | 10 可以建立这样一个函数，对于一个特定的点，只可能有最多4个方向可以移动，可以从
（0，0）开始，计算每个位置的距离，取最小值:
min(当前位置，左移动（可以的话），右移动（可以的话），上移动（可以的话），下
移动（可以的话））
终止条件是无法移动了。这个算法对于有block的也适用。 |
w****a
发帖数: 710 | |
h**********c
发帖数: 4120 | 12 很看成最短路径怪
那捂空捉了来，一棒打去
岂不是到了西天
【在 b******i 的大作中提到】
: find a intersection to build office so that the sum of all employees’
: commute distances is minimum. （the map is represented as a m*n grid, you
: are given each employee’s coordination, they can only move in up-down and
: left-right directions）
: 这是Google一道面试题。我能想到的就是从每个employee做BFS，再求出非employee的
: 格子的最短路径之和。找个和最小的格子。请问这题还有更简单的方法吗？
|
h**********c
发帖数: 4120 | 13 那武松听了
也把那怪捉来，一棒打去
却打出景阳冈的exception
【在 h**********c 的大作中提到】
: 很看成最短路径怪
: 那捂空捉了来，一棒打去
: 岂不是到了西天
|
