g********s
发帖数: 25 | 1 实在没信心在这么短时间写出来。 请问一下，有没有低效一点但是简单一点的解法。
（递归+剪枝不算） 问题是 K nearest neighbors. |
w******j
发帖数: 185 | |
A***o
发帖数: 358 | 3 用quick select的思路不行吗
【在 g********s 的大作中提到】
: 实在没信心在这么短时间写出来。 请问一下，有没有低效一点但是简单一点的解法。
: （递归+剪枝不算） 问题是 K nearest neighbors.
|
g********s
发帖数: 25 | 4 quick select 解决 k nearest neighbors ??
【在 A***o 的大作中提到】
: 用quick select的思路不行吗
|
A***o
发帖数: 358 | 5 低效简单 O(n)
1. 算到所有点距离
2. 任选一距离， 两分
3. update k, 重复2
典型quick select
【在 g********s 的大作中提到】
: quick select 解决 k nearest neighbors ??
|
g********s
发帖数: 25 | 6 噢。 这个题的意思是 找出在所有点集中找出最接近的k个点（looks like a cluster)
。 而你的解法是知道一个点，找跟它最近的k个。
【在 A***o 的大作中提到】
: 低效简单 O(n)
: 1. 算到所有点距离
: 2. 任选一距离， 两分
: 3. update k, 重复2
: 典型quick select
|
o*****n
发帖数: 189 | 7 算出所有点 到点距离，然后根据到每一点的距离排序。
找到第k-1个距离最小的那个排序。
最慢的方法？ |
