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个数排序吗？
|
|
