3

CareerCupで Google インタビューの質問を見つけました

2D 平面が与えられ、そこに約 6000 の点があるとします。最も多くの点を通過する直線を見つけます。

そこにある多くの回答は、この質問は難しく、ある種の特別なアルゴリズムが関係していると言っています。

しかし、私の見解は異なり、おそらく私は間違っています。

ここに私の考えがあります：

まず、2D 平面に座標系を与えます。したがって、すべてのポイントには一意の x と y があり{x, y}ます。簡単にするために、座標系を{0, 0}平面全体の左下に置くことができます。したがって、すべての x と y は 0 より大きくなります。

それから私は理論を持っています：

複数の点が同じ線上にある場合は、次の 3 つのケースのいずれかである必要があります。

  1. それらのx値は同じです
  2. それらのy値は同じです
  3. x/yまたはy/x値は同じです。しかし、x/yケースはケースと同じy/xなので、 だけに注目しましょうx/y。

次に、3 つのハッシュテーブルを作成します。

  1. 最初のもの ( hashtable-x) は のキーでx、値は同じ を持つポイントのリストxです。

  2. 2 番目のもの ( hashtable-y) は のキーでy、値は同じを持つポイントのリストyです。

  3. 最後の ( hashtable-x-y) は のキーでx/y、値は同じを持つポイントのリストx/yです。

次に、6000 ポイント全体をスキャンします。各ポイントについて、xから取得し、そのhashtable-xポイントをそのスロットの値 (リスト) に入れます。次に、 と と同様のことをhashtable-y行いhashtable-x-yます。

最後に、3 つのハッシュテーブルのすべてのリストをスキャンし、最も長いリストに目的のラインのポイントが含まれていることを確認します。

私のアルゴリズムをどう思いますか？

わかりました、ここに重複があります。以前にその質問を見つけられなかったことをお詫びします。

ほとんどの点を通る直線を見つける最も効率的なアルゴリズムは何ですか?

4

2 に答える 2

2

あなたのアルゴリズムは述べられたように機能しません。多くの点がy=2x + 1の線上にあると考えてください。つまり、（1,3）、（2,5）、（3,7）、（4,9）、および（5,11）が得られます。

計算幾何学の大学院レベルのコースがない限り、これを解決することは期待されていないと思います。取り決めは、ポイントラインの双対性を使用して、すべてのポイントを双対空間のラインに変換し、ほとんどのラインが交差するポイントを見つけることです。単純に、O（n ^ 2）でこれを行うには、線のすべてのペアを調べ、それらが分析形式で交差する場所を評価します。また、平面スイープスタイルのアルゴリズムを使用してO（n log n）を実行できると思いますが、詳細はわかりません。

于 2012-06-07T14:34:43.350 に答える
0

ここでの回答では、ポイント数が 2 以上であると仮定します (ゼロと 1 ポイントは些細なケースです)。

最初に、そのような線は少なくとも 2 つのポイントを通過する必要があることに注意してください。したがって、次のようにソリューションを構築できます。

for each pair of points p1,p2
    find equation of the line l passing through p1,p2

    for each point p3 not p1 or p2
        if p3 lies on l
            counter[l]++

return argmax(counter)
于 2012-06-07T15:14:01.587 に答える