4

我正在查看以下面试问题：

给定 2d 坐标，找到离原点最近的 k 个点。提出一种存储点的数据结构和获取k个点的方法。还要指出代码的复杂性。

我想出的解决方案是将二维点保存在一个数组中。对于前k个点，找到每个点到原点的距离并建立一个最大堆。对于剩余的点，计算与原点的距离，比如 dist。如果 dist 大于堆的最顶部元素，则将堆的最顶部元素更改为 dist 并运行该heapify()过程。

这将需要O(k)构建堆和O((n-k)log k)过程heapify()，因此总复杂度 = O(n log k).

任何人都可以提出更好的数据结构和/或方法，并且效率也可能更高吗？

编辑

其他一些数据结构在这里有用吗？

4

3 回答 3

3

您正在寻找的是部分排序。

我认为最好的方法是将所有内容放入未排序的数组中，然后使用修改后的就地快速排序，忽略索引完全高于或完全低于的分区k，并使用与原点的距离作为比较。

来自上面维基百科文章的伪代码：

function quickfindFirstK(list, left, right, k)
     if right > left
         select pivotIndex between left and right
         pivotNewIndex := partition(list, left, right, pivotIndex)
         if pivotNewIndex > left + k  // new condition
             quickfindFirstK(list, left, pivotNewIndex-1, k)
         if pivotNewIndex < left + k
             quickfindFirstK(list, pivotNewIndex+1, right, k+left-pivotNewIndex-1)

执行后，这会将最小的k项目留在第一个k位置，但不按顺序排列。

于 2012-07-28T16:35:10.067 回答
1

我会为此使用订单统计信息。
请注意，我们使用了一个SELECT使用与原点的距离作为比较函数的修改。

  • 将元素存储在数组A中，第一个元素是A[1]，最后一个元素是A[n]。
  • 运行SELECT(A,1,n,k)以找到k最接近原点的元素。
  • 返回元素A[1..k]。

它的好处之一SELECT是对输入进行分区，以便将最小的k-1元素留给A[k].

因此将元素存储在数组中是O(n).
跑步SELECT是O(n)。
返回请求的元素是O(1).

于 2012-07-28T16:25:44.910 回答
1

我使用所谓的“部分排序”为您编写了一个简单的版本 http://tzutalin.blogspot.sg/2017/02/interview-type-questions-minqueue.html

public static void main(String[] args) {
    Point[] points = new Point[7];
    points[0] = new Point(0, 0);
    points[1] = new Point(1, 7);
    points[2] = new Point(2, 2);
    points[3] = new Point(2, 2);
    points[4] = new Point(3, 2);
    points[5] = new Point(1, 4);
    points[6] = new Point(1, 1);
    int k = 3;
    qSelect(points, k - 1);
    for (int i = 0; i < k; i++) {
        System.out.println("" + points[i].x + "," + points[i].y);
    }
    // Output will be
    //        0,0
    //        1,1
    //        2,2
}

// in-place qselect and zero-based
static void qSelect(Point[] points, int k) {
    int l = 0;
    int h = points.length - 1;
    while (l <= h) {
        int partionInd = partition(l, h, points);
        if (partionInd == k) {
            return;
        } else if (partionInd < k) {
            l = partionInd + 1;
        } else {
            h = partionInd - 1;
        }
    }
}

static int partition(int l, int h, Point[] points) {
    // Random can be better
    // int p = l + new Random.nextInt(h - l + 1);
    int p = l + (h - l) / 2;
    int ind = l;
    swap(p, h, points);
    Point comparePoint = points[h];
    for (int i = l; i < h; i++) {
        if (points[i].getDistFromCenter() < comparePoint.getDistFromCenter()) {
            swap(i, ind, points);
            ind++;
        }
    }
    swap(ind, h, points);
    return ind;
}

static void swap(int i, int j, Point[] points) {
    Point temp = points[i];
    points[i] = points[j];
    points[j] = temp;
}
于 2017-02-05T10:26:00.200 回答