4

私は次のインタビューの質問を見ています：

2次元座標が与えられた場合、原点に最も近いk点を見つけます。ポイントを格納するためのデータ構造とkポイントを取得する方法を提案します。また、コードの複雑さも指摘してください。

私が理解した解決策は、2Dポイントを配列に保存することです。最初の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]。

入力を分割することの利点の1つである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 に答える