在二维平面中找到K最近点到点P.

Question

资料来源:AMAZON访谈问题

给定点P和二维空间中的其他N个点,找到最接近 P 的N个点中的K个点.

这样做的最佳方式是什么？

这个Wiki页面在构建算法时没有提供太多帮助.任何想法/接近人.

Answer 1

解决方案1使堆大小为K并通过最小距离O(NLogK)复杂度收集点.

解决方案2:获取大小为N的数组并按距离排序.应该使用QuickSort(Hoare修改).作为答案采取前K点.这也是NlogN的复杂性,但可以优化以近似O(N).如果跳过不必要的子数组的排序.当您将数组拆分为2个子数组时,您应该只接受Kth索引所在的数组.复杂度将是:N + N/2 + N/4 + ... = O(N).

解决方案3:在结果数组中搜索Kth元素并获取所有小点然后建立.存在O(N) alghoritm,类似于搜索中位数.

注意:最好使用sqr of distance来避免sqrt操作,如果point有整数坐标,它会更快.

面试答案更好地使用解决方案2或3.

Answer 2

只需一个查询...

保持一堆大小k.

对于每个点,计算到该点的距离P.将该距离插入堆中,如果堆的大小大于,则从堆中删除最大值k.

运行时间: O(n log k)

Answer 3

解决方案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;
    }
}