在二维平面上找到离点P最近的K个点
26
- Spandan
4
我把你平衡到零了 ;) 答案随后会跟进。 - Толя
2这只是“查找k个最小数”的变体。只不过你需要计算每个点的距离。 - Ingo
@Ingo "计算每个点的距离" ... 你是说这是蛮力算法？ - Spandan
由于斐波那契堆具有O(1)插入和O(log n)删除，它们是否应该允许O(n + k log n)或O(n + k log k)的解决方案？ - xjcl
9个回答
39
解决方案1：创建大小为K的堆，并按最小距离收集点，时间复杂度为O(NLogK)。
解决方案2：创建大小为N的数组并按距离排序。应该使用快速排序（Hoare修改版）。作为答案，请取前K个点。虽然时间复杂度为NlogN，但可以优化到近似O(N)。如果跳过不必要的子数组排序。当您将数组分成2个子数组时，只需取包含第K个索引的数组即可。时间复杂度为：N + N/2 + N/4 + … = O(N)。
解决方案3：在结果数组中查找第K个元素，并获取所有小于所找到的点。存在O(N)算法，类似于查找中位数。
注：最好使用距离的平方避免进行sqrt运算，如果点坐标为整数，则更快。
作为面试答案，最好使用解决方案2或3。
- Толя
6
你能更详细地解释一下第三种解决方案吗？它似乎与第二种解决方案非常相似。 - Bernhard Barker
1解决方案3是快速选择算法。将所有距离存储在一个数组中。使用类似于快速排序（第9章CLRS）的方法找到给出第k个最小元素的索引，然后从索引0到k-1的元素将给出所有所需的k个点。 - Shankhoneer Chakrovarty
2解决方案2和3中的O（N）是平均情况下的复杂度。最坏情况仍然是O（NLogK）。 - Kunal Balani
@KunalBalani 难道最坏情况的复杂度不应该是O(NK)吗？（例如，在每轮快速选择分区中窗口大小仅减少1的情况下，如果数组已经排序并且您继续选择最后一个元素作为枢轴） - htompkins
如何在排序之前找到必须跳过的数组？ - voipp
第二种解决方案被称为“快速选择”，也可以考虑作为第三种方案的组合。https://zh.wikipedia.org/wiki/Quickselect - Nuclearman
5
解决方案1
private List<Point> nearestKPoint_1(List<Point> list, final Point center, int k) {
List<Point> ans = new ArrayList<>();
PriorityQueue<Point> maxHeap = new PriorityQueue<>(k + 1, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return distance(center, o2) - distance(center, o1);
}
});
for (Point p : list) {
maxHeap.offer(p);
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
Iterator<Point> i = maxHeap.iterator();
while (i.hasNext()) {
ans.add(i.next());
}
return ans;
}
public int distance(Point p1, Point p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
if (x != point.x) return false;
return y == point.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}
解决方案2
private List<Point> nearestKPoint_2(List<Point> list, final Point center, int k) {
List<Point> ans = new ArrayList<>();
Distance[] nums = new Distance[list.size()];
for (int i = 0; i < nums.length; i++) {
nums[i] = new Distance(distance(center, list.get(i)), i);
}
quickSelect(nums, k);
for (int i = 0; i < k; i++) {
ans.add(list.get(nums[i].i));
}
return ans;
}
private void quickSelect(Distance[] nums, int k) {
int start = 0, end = nums.length - 1;
while (start < end) {
int p = partition(nums, start, end);
if (p == k) {
return;
} else if (p < k) {
start = p + 1;
} else {
end = p - 1;
}
}
}
private int partition(Distance[] nums, int start, int end) {
Distance pivot = nums[start];
int i = start, j = end + 1;
while (true) {
while (i < end && nums[++i].compareTo(pivot) < 0);
while (j > start && nums[--j].compareTo(pivot) > 0);
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, start, j);
return j;
}
private void swap(Distance[] nums, int i, int j) {
Distance tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
class Distance implements Comparable<Distance> {
int d;
int i;
public Distance(int d, int i) {
this.d = d;
this.i = i;
}
@Override
public int compareTo(Distance o) {
return this.d - o.d;
}
}
- hotpro
2
如果输入不是方便的点类型，而是一个点矩阵，例如[[3,4],[1,2],[5,3]]，那么代码会有什么不同？在这种情况下，我真的找不到任何直接访问x y值的方法。 - Bryan B.
只需提一下，比较器可以像下面这样定义:
PriorityQueue maxHeap = new PriorityQueue((a, b) -> distance(a, center) - distance(b, center)); - elulcao4
你可以使用KD树 http://en.wikipedia.org/wiki/K-d_tree 来划分空间，并且通过二进制搜索逐步查找邻居。使用此方法的好处是，它易于扩展为在线版本，当你在运行时逐个或批量接收数据点/查询时。
- fury
0
// point_type pt, length_sq(p) { return pt[0] * pt[0] + pt[1] * pt[1]}
// std::vector<point_type> points to search.
// The algorithm should recursion depth to
// O(k * log(points.size())), and
// running time to O(points.size()).
std::nth_element(
points.begin(),
points.begin() + k,
points.end(),
[&pt](point_type const & a)
{
return length_squared(a - pt);
});
// points[0], ... , points[k - 1] are the closest points to pt
- Catriel
0
C#使用LINQ的解决方案
public int[][] KClosest(int[][] points, int[][] p, int K) {
var orderedPoints = points.OrderBy(point => Math.Pow(point[0]-p[0], 2) + Math.Pow(point[1]-p[1], 2));
return orderedPoints.Take(K).ToArray();
}
- havij
2
这个解决方案是找到距离原点最近的点，而不是另一个点P。 - elulcao
@elulcao 谢谢你指出这个问题，它很容易修复。 - havij
0
class Solution {
public int[][] kClosest(int[][] points, int K) {
double [] combinationArr = new double[points.length];
Hashtable<Double,int[]> pt = new Hashtable();
for (int i = 0; i <points.length; i++) {
int [] in = points[i];
for (int j = 0; j < in.length - 1; j++) {
Integer x = in[j];
Integer y = in[j + 1];
double powerX=Math.pow(x, 2);
double powerY = Math.pow(y, 2);
double combination= (Double)(Math.sqrt(powerX + powerY));
pt.put(combination, points[i]);
combinationArr[i] = combination;
}
}
Arrays.sort(combinationArr);
int [][] kpoints = new int[K][K];
for (int n = 0; n < K; n++) {
kpoints[n] = pt.get(combinationArr[n]);
}
return kpoints;
}
}
- issam
-1
以下方法有什么问题吗？
1）计算给定点到其他点的距离。
2）将该点的距离和索引存储到
3）从map中选择前K个元素。它们的值将给出points数组中Point元素的索引。
该map按其键的自然顺序排序，或者按创建时提供的比较器排序。
1）计算给定点到其他点的距离。
2）将该点的距离和索引存储到
TreeMap<Double,Integer> map中。3）从map中选择前K个元素。它们的值将给出points数组中Point元素的索引。
该map按其键的自然顺序排序，或者按创建时提供的比较器排序。
- Harshit
1
你的算法的运行时间能得到的话会很好。 (1) 是O（n）。 (2) 取决于TreeMap的实现，如果是Java TreeMap，则保证put和get的log N，并维护元素的排序顺序。 因此，（2）是O（n log n），（3）是O（k log n）。 总运行时间为O（（n + k）log n）。 - Kent Munthe Caspersen
-2
public static void NearestPoints() {
int[][] Points = { new int[] { -16, 5 },
new int[] { -1, 2 },
new int[] { 4, 3 },
new int[] { 10, -2 },
new int[] { 0, 3 },
new int[] {- 5, -9 } };
// Linq Order by default use quick sort which will be best suited in this.
var orderPoint = from i in Enumerable.Range(0, Points.Length)
orderby Math.Sqrt( Points[i][0] * Points[i][0]
+ Points[i][1] * Points[i][1] )
select new int[][] { Points[i] };
var result = orderPoint.Take(3);
}
- NishiKant Goutam
1
这并没有真正回答问题，问题是要求一般解决方案，而不是一个特定的代码片段来解决问题的单个实例。 - Z4-tier
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接