使用してC++正しく

Question

この質問はインタビューで頼まれたPRIORITY_QUEUEコンパレータは最近

public interface PointsOnAPlane { 

/** 
* Stores a given point in an internal data structure 
*/ 
void addPoint(Point point); 

/** 
* For given 'center' point returns a subset of 'm' stored points that are 
* closer to the center than others. 
* 
* E.g. Stored: (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) 
* 
* findNearest(new Point(0, 0), 3) -> (0, 1), (0, 2), (0, 3) 
*/ 
vector<Point> findNearest(vector<Point> points, Point center, int m); 

} 

私は を使用この従っているアプローチは）最も近いポイントを保存するために、最大ヒープPRIORITY_QUEUEを作成 priority_queue<Point,vector<Point>,comp> pq;

2）ポイントベクトルを反復し、優先キューサイズが<の場合はポイントをプッシュします。

3）サイズ== mが現在ポイントとキューのトップを比較し

必要

for(int i=0;i<points.size();i++) 
{ 
    if(pq.size() < m) 
    { 
     pq.push(points[i]); 
    } 
    else 
    { 
     if(compareDistance(points[i],pq.top(),center)) 
     { 
     pq.pop(); 
     pq.push(points[i]); 
     } 
    } 
} 

4）最後に、ベクターにプライオリティキューの内容を入れて返す場合ポップ場合。

コンパレータとcompareDistanceコンパレータを使って最初にm点を保存し、現在の点と上の点を比較する方法を教えてください。

Answer 1

私はあなたのアプローチが異なる方法でpriority_queueを使用するように変更できると思います。 forループにif文があり、このif文はpriority_queueにいつ追加するかを制御するため、コードは少し複雑になります。最初にpriority_queueにすべてのポイントを追加してから、mポイントを飛ばしてみませんか？ priority_queueにすべての作業をさせてください。

priority_queueを使用してfindNearest関数を実装するためのキーは、コンパレータがcenterパラメータをキャプチャするラムダであることを認識することです。だからあなたはそういうことをすることができます：

#include <queue> 
#include <vector> 
using namespace std; 

struct Point { int x, y; }; 

constexpr int distance(const Point& l, const Point& r) 
{ 
    return (l.x - r.x)*(l.x - r.x) + (l.y - r.y)*(l.y - r.y); 
} 

vector<Point> findNearest(const vector<Point>& points, Point center, int m) 
{ 
    auto comparator = [center](const Point& l, const Point& r) { 
     return distance(l, center) > distance(r, center); 
    }; 

    priority_queue<Point, vector<Point>, decltype(comparator)> pq(comparator); 

    for (auto&& p : points) { 
     pq.emplace(p); 
    } 

    vector<Point> result; 
    for (int i = 0; i < m; ++i) { 
     result.push_back(pq.top()); 
     pq.pop(); 
    } 

    return result; 
} 

また、アルゴリズムの欠陥について話すのも良いです。

この実装はO(nlogn)で実行されます。特に、最も近いmポイントしか必要としないので、この実行時間に勝る巧妙なアルゴリズムが存在します。

キューのためにO(n)が使用されています。これにより、よりうまく処理できるはずです。この関数で実際に起こっていることは並べ替えであり、並べ替えはインプレースで実装できます。

整数オーバーフローが起こりやすい。良い考えは、Point構造体上のテンプレートを使用することです。また、テンプレートを使用して、findNearest関数で汎用のコンテナを作成することもできます。コンテナは反復をサポートするだけです。