p******m 发帖数: 154 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: peachgcm (peach), 信区: JobHunting
标 题: 欢迎大家积极讨论一个ms简单的算法面试题
发信站: BBS 未名空间站 (Sat Mar 20 19:30:47 2010, 美东)
在real line上给出n个数,找出k个数,such that the sum of squares of distances
is minimized。例如,assume c是
这k个数的几何zhongxin。c = (n1+...+nk)/k 。 Then 目标函数就是: (n1-
c)^2+...+(nk-c)^2 | l******e 发帖数: 470 | 2 key:k个数是连续的
然后就那么O(n)个选择,挨个试
distances
【在 p******m 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: peachgcm (peach), 信区: JobHunting : 标 题: 欢迎大家积极讨论一个ms简单的算法面试题 : 发信站: BBS 未名空间站 (Sat Mar 20 19:30:47 2010, 美东) : 在real line上给出n个数,找出k个数,such that the sum of squares of distances : is minimized。例如,assume c是 : 这k个数的几何zhongxin。c = (n1+...+nk)/k 。 Then 目标函数就是: (n1- : c)^2+...+(nk-c)^2
| p******m 发帖数: 154 | | l****u 发帖数: 4594 | 4 似乎是找k个variance最小的数;
distances
【在 p******m 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: peachgcm (peach), 信区: JobHunting : 标 题: 欢迎大家积极讨论一个ms简单的算法面试题 : 发信站: BBS 未名空间站 (Sat Mar 20 19:30:47 2010, 美东) : 在real line上给出n个数,找出k个数,such that the sum of squares of distances : is minimized。例如,assume c是 : 这k个数的几何zhongxin。c = (n1+...+nk)/k 。 Then 目标函数就是: (n1- : c)^2+...+(nk-c)^2
| D****A 发帖数: 360 | 5 下面的解法不一定最优,只是我能想到的:
如果n个数不是排好序的话,先扫描一遍,找出最大最小,n_min和n_max;
把[n_min, n_max]分出n-1个等长的子区间[m1, m2),[m2, m3) ... 然后把n个数分到n
-1个bucket里;
找出所有的区间[mj, mk+1), s.t. [mj, mk)包含至多k-1个数,[mj, mk+1)包含至少k
个数
在这些[mj, mk+1)内部先计算最小k方差,再从所有这些区间中找k方差最小的。
distances
【在 p******m 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: peachgcm (peach), 信区: JobHunting : 标 题: 欢迎大家积极讨论一个ms简单的算法面试题 : 发信站: BBS 未名空间站 (Sat Mar 20 19:30:47 2010, 美东) : 在real line上给出n个数,找出k个数,such that the sum of squares of distances : is minimized。例如,assume c是 : 这k个数的几何zhongxin。c = (n1+...+nk)/k 。 Then 目标函数就是: (n1- : c)^2+...+(nk-c)^2
| H*******g 发帖数: 1477 | 6 distances是指数值的差还是各个数的位置的距离啊?
这些数的大小有规律吗?什么是real line?
distances is minimized。
【在 p******m 的大作中提到】 : 你的意思是先将n个数排序吗?
|
|