使用C++ priority_queue比較正確

這個問題被問近日在接受採訪使用C++ 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); 

}

這是我用

1以下辦法）創建最大堆priority_queue存儲最近點 priority_queue<Point,vector<Point>,comp> pq;

2）迭代點向量並推送一個點，如果優先級隊列大小爲< m

3）如果尺寸==米然後比較隊列頂部與當前點和彈出如果必要

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）最後把優先級隊列中的內容在載體並返回。

我應該如何編寫comp和compareDistance比較器，以便我可以最初存儲m個點，然後將當前點與頂部點進行比較？

來源

2017-06-29 msd_2

分享一個想法。我們可以使用像四元樹或者網格這樣的空間劃分。因此當中心發生變化時，我們不需要度假點或者重建priority_queue。 –

爲什麼你需要優先隊列？ 1.測量到所有點的距離。存儲距離點（或點索引）到一個矢量，2 partial_sort這個矢量3.複製結果 – Alexander

'public interface ...'你確定它是C++嗎？ – moooeeeep

我認爲你的方法可以改變，以便以不同的方式使用priority_queue。代碼變得有點複雜，因爲for循環中有一個if語句，並且此if語句控制何時將其添加到priority_queue。爲什麼不先把所有的積分加到priority_queue上，然後彈出m點？讓priority_queue完成所有工作。

使用priority_queue實現findNearest函數的關鍵是實現比較器可以是捕獲中心參數的lambda。所以你可以這樣做：

#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結構上使用模板。您還可以使用模板使points容器在findNearest函數中具有通用性。容器只需支持迭代。

來源

2017-06-29 08:35:32 jgcoded

使用C++ priority_queue比較正確

回答

相關問題