我在 LeetCode 上解決了這個問題 - https://leetcode.com/problems/k-closest-points-to-origin/
我可以做兩件事 - 1）我們需要按升序對給定點的距離進行排序。
2）我們還必須有與原點距離相關的點。
經過頭腦風暴，我想出了使用 c stl 中的地圖的想法。因為他們會負責排序以及距離和點的關聯。我的代碼如下 -
class Solution
{
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k)
{
map<double,vector<int>> m;
vector<vector<int>> answer;
for (int i = 0; i < points.size(); i )
{
double x = sqrt((points[i][0] * points[i][0]) (points[i][1] * points[i][1]));
m.insert(pair<double, vector<int>>(x,{points[i][0], points[i][1]}));
}
for (int i = 0; i < k; i )
{
auto it = m.begin();
advance(it,i);
answer.push_back(it->second);
}
return answer;
}
};
對于前 2 個測驗用例，它作業正常并拋出運行時錯誤 - 堆疊緩沖區溢位，我最初使用 float 表示 x 但我認為由于限制它會導致錯誤，所以我將型別更改為 double 但仍然沒有運氣！
如果有人能幫我找出這里的錯誤，那將是一個很大的幫助。先感謝您！
uj5u.com熱心網友回復：
假設有兩個點 [-1, 0] 和 [0, 1]，k 的值為 2。如果你使用 map，你的情況只會得到 1 個 <key, value> 對，因為密鑰（在本例中為 sqrt(1)）對于兩個點都是相同的。因此，您需要使用multimap，您可以在其中多次使用相同的鍵。在這里閱讀。
基于您的代碼的作業代碼示例：
class Solution
{
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k)
{
multimap<int,vector<int>> m;
vector<vector<int>> answer;
for (int i = 0; i < points.size(); i )
{
int x = (points[i][0] * points[i][0]) (points[i][1] * points[i][1]);
m.insert(pair<int, vector<int>>(x,{points[i][0], points[i][1]}));
}
int i = 0;
for (auto it = m.begin(); it != m.end() && i < k; it , i ) {
//cout << it->first << " : " << it->second[0] << ", " << it->second[1] << endl;
answer.push_back(it->second);
}
return answer;
}
};
建議：
- 您無需擔心是將距離值存盤為 double 還是 float。由于您將 sqrt(some_value1) 與 sqrt(some_value2) 進行比較，因此您可以完全省略 sqrt。
- std::advance 具有線性時間復雜度。您可以在 for 回圈的開頭簡單地初始化迭代器，并使用 運算子遞增。該運算子具有恒定的時間復雜度。在此處閱讀有關 std::advance 的更多資訊。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/408003.html
標籤：
上一篇：C 懸空參考奇怪的行為