b*****i
发帖数: 130 | 1 刚面的。。。
第二题跪了。。
1. 3sum
Given an array of integers
[1, 2, -3, 4, 0]
To find any 3 numbers in array such that they sum to zero.
eg:
1) 1 , 2, -3
2) 0, 0, 0
2. Q2: Given set of points in 2d grid space. Find a grid point such that sum
of distance from all the points to this common point is minimum.
eg: p1: [0, 0] p2: [3, 0] p3: [0, 3]
ans: r: [0,0]
sum: 0 + 3 + 3 = 6
for every other point sum to this ans greater than 6.
实在不知道是啥，乱说了个找mininum manhattan distance,然后赶紧临时google下，
貌似是找median，然后对方说能不能证明一下。。表示不会。。。
这题正解到底是啥？ |
s****p
发帖数: 28 | 2 这不是坑人吗 看了wiki老半天大概懂了 请问这是否面试官就是想挂人 |
f**********e
发帖数: 288 | |
g***j
发帖数: 1275 | 4 你确定第二题理解对了？
sum
【在 b*****i 的大作中提到】
: 刚面的。。。
: 第二题跪了。。
: 1. 3sum
: Given an array of integers
: [1, 2, -3, 4, 0]
: To find any 3 numbers in array such that they sum to zero.
: eg:
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 2. Q2: Given set of points in 2d grid space. Find a grid point such that sum
|
b*****i
发帖数: 130 | 5 就是不知道第二题该咋做才来版上问问大家的嘛。。
【在 g***j 的大作中提到】
: 你确定第二题理解对了？
:
: sum
|
z**8
发帖数: 127 | 6 可以用dp吧，table 保存两点间距离，然后一行行扫，找最小和的点。不知道对不对。 |
r****s
发帖数: 1025 | 7 bruteforce 不就是O(n^2)?
wiki链接在哪里？ |
l*****a
发帖数: 14598 | 8 到底是点集中的一点
还是任意的一点
【在 b*****i 的大作中提到】
: 就是不知道第二题该咋做才来版上问问大家的嘛。。
|
l*********8
发帖数: 4642 | 9 re, that's the point.
【在 l*****a 的大作中提到】
: 到底是点集中的一点
: 还是任意的一点
|
b*****i
发帖数: 130 | 10 呀，忘记问了。。。
我当时理解的是任意一点。。。然后就觉得好难。。然后就完全stuck了。。
【在 l*********8 的大作中提到】
: re, that's the point.
|
|
|
W*********y
发帖数: 481 | 11 第2题到底怎么理解？到任一网格点的话，给的例子答案不应该是 (1,1) ？到三点距
离和为 5.89
sum
【在 b*****i 的大作中提到】
: 刚面的。。。
: 第二题跪了。。
: 1. 3sum
: Given an array of integers
: [1, 2, -3, 4, 0]
: To find any 3 numbers in array such that they sum to zero.
: eg:
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 2. Q2: Given set of points in 2d grid space. Find a grid point such that sum
|
s****p
发帖数: 28 | 12 wikipedia search Geometric Median
【在 r****s 的大作中提到】
: bruteforce 不就是O(n^2)?
: wiki链接在哪里？
|
b*****c
发帖数: 1103 | 13 不是歐幾粒得距離是紐約曼哈頓距離
【在 W*********y 的大作中提到】
: 第2题到底怎么理解？到任一网格点的话，给的例子答案不应该是 (1,1) ？到三点距
: 离和为 5.89
:
: sum
|
a***n
发帖数: 623 | 14 这……不会这么变态吧，求多点集的费马点？证明很难的吧。。 |
e***l
发帖数: 710 | |
l*****a
发帖数: 14598 | 16 怎么证明呢
【在 e***l 的大作中提到】
: x y 轴分别找median即可
|
s***5
发帖数: 2136 | 17 班上码公们的数学水平有待提高，证明很简单啊。
点集 {x_1, x_2, ..., x_n}，设求的点为x，Manhattan distance的话对下面的和求导
即可解方程即可。
sum(|x-x_i|)|i = 1,2 .., n
即sum(sign(x-x_i)) = 0
唯一的解x必须为{x_i}的中位数，这样一半为+1，一半为-1，和为0. |
r****7
发帖数: 2282 | 18 x y轴的median不一定是同一个点啊
我觉得是先sort，比如按x轴，如果x相同的按y sort，然后按这个顺序建一个树，找到
树的中点，就是这个点吧。
【在 e***l 的大作中提到】
: x y 轴分别找median即可
|
l*****8
发帖数: 1083 | 19 第二题比第一题还简单，O(n^2)暴力循环一下就好了，lz没理解题意
果然lz是女生，感觉题出地简单。。。 |
f*******w
发帖数: 1243 | 20
什么叫不一定是同一个点……
x轴的median确定x坐标，y轴的median确定y坐标啊
【在 r****7 的大作中提到】
: x y轴的median不一定是同一个点啊
: 我觉得是先sort，比如按x轴，如果x相同的按y sort，然后按这个顺序建一个树，找到
: 树的中点，就是这个点吧。
|
|
|
f*******w
发帖数: 1243 | 21 第二题还有个加强版，就是每个点是有weight的 |
l*****8
发帖数: 1083 | 22 这个加强没什么意思吧，算法一模一样的，就是计算距离的时候多乘上个weight
【在 f*******w 的大作中提到】
: 第二题还有个加强版，就是每个点是有weight的
|
r****7
发帖数: 2282 | 23 是说这个点不用在这个set里？
【在 f*******w 的大作中提到】
: 第二题还有个加强版，就是每个点是有weight的
|
d********t
发帖数: 9628 | 24 RE
【在 s***5 的大作中提到】
: 班上码公们的数学水平有待提高，证明很简单啊。
: 点集 {x_1, x_2, ..., x_n}，设求的点为x，Manhattan distance的话对下面的和求导
: 即可解方程即可。
: sum(|x-x_i|)|i = 1,2 .., n
: 即sum(sign(x-x_i)) = 0
: 唯一的解x必须为{x_i}的中位数，这样一半为+1，一半为-1，和为0.
|
C********e
发帖数: 492 | 25 第二题不就是求个重心么？直接O（1）算出来……
sum
【在 b*****i 的大作中提到】
: 刚面的。。。
: 第二题跪了。。
: 1. 3sum
: Given an array of integers
: [1, 2, -3, 4, 0]
: To find any 3 numbers in array such that they sum to zero.
: eg:
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 2. Q2: Given set of points in 2d grid space. Find a grid point such that sum
|
c******e
发帖数: 558 | |
e***g
发帖数: 57 | 27 The second question says "find a grid point", which means the answer is any
point on the grid. 2-D Manhattan distance is simply the sum of the x
dimension distance and the y dimension distance. So to prove the median
point is the answer, we only need to prove the 1-D case. Prove as follows:
1. In 1-D grid, assume the number of nodes at both sides of the median point
is N (N>=0), the number of nodes on the median point is M (M>=0).
2. If we choose a grid point at the right/left of the median point, we will
increase the total distance by (N + M)*1 and decrease the total distance by
(N*1). The total change of distance is (N + M) * - N*1 = M. Because M>=0,
the total distance is always larger or equal to the total distance from all
nodes to the median point. Thus, the median point has the smallest total
distance.
Pay attention, it's Manhattan distance not Euclidean distance, so the answer
is not center of mass. |
z***m
发帖数: 1602 | 28 不是重心，因为这儿是grid，比如说是3rd ave and 4th dr交界处, 不能说在3.14 ave
和 4.125 dr交界处
【在 C********e 的大作中提到】
: 第二题不就是求个重心么？直接O（1）算出来……
:
: sum
|
C********e
发帖数: 492 | 29 领会意思就是了，具体细节具体做的时候考虑。
比如你Argu算出来具体数不一定是grid点，那么算出来后test一下所在格点周边几个点
就可以了。仍然是O(1)
ave
【在 z***m 的大作中提到】
: 不是重心，因为这儿是grid，比如说是3rd ave and 4th dr交界处, 不能说在3.14 ave
: 和 4.125 dr交界处
|
z****j
发帖数: 111 | 30 解是求两个轴的median， 但是怎么证明呢？
【在 f*******w 的大作中提到】
: 第二题还有个加强版，就是每个点是有weight的
|
