狗onsite面试

alinawxn 发表于 2019-2-19 23:52
第一题如果是奇数的话取中间那个左边，偶数的话中间两点间任意坐标

对的，就是取 Median.

kkchenk 发表于 2019-2-19 21:37
请教y坐标 medium 怎么实现o(logN)呢 要排序的话不是O(nlogn)吗

可以O(n)求Median，不用排序。

liaohs49 发表于 2019-2-19 20:43
第一题全部加起来取平均就行吧o（n）

不对，不是取平均

yuhaoz3 发表于 2019-2-19 14:20
为啥只有两题

估计是intern转fulltime吧

第一题296？

mark下加分了

min sum|yi-y| 结果是median(yi)
min sum|yi-y|^2 结果是mean(yi)
由于是垂直方向，所以直接|yi-y|代表距离，所以这题应该是median值。

liaohs49 发表于 2019-2-19 20:43
第一题全部加起来取平均就行吧o（n）

为什么不是中位数？

jerry848 发表于 2019-2-20 02:42
不对，不是取平均

如果个数是偶数的话，好像取中间两个数任意值都行，比如1,2,3,4，可以取2~4之间，都可以的。
但如果个数是奇数的话，就只能取中位数了。

zhangyilong 发表于 2019-2-21 02:06
如果个数是偶数的话，好像取中间两个数任意值都行，比如1,2,3,4，可以取2~4之间，都可以的。
但如果个数 ...

对。这道题的关键是O(n)时间求Median