什么导致堆栈缓冲区溢出？

Question

我在 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 个测试用例工作正常并抛出运行时错误 - 堆栈缓冲区溢出，我最初对 x 使用 float 但我认为是因为限制导致了错误，所以我将类型更改为 double 但是仍然没有运气！

如果有人能帮我找出这里的错误，那将是一个很大的帮助。提前致谢！

Answer 1

假设有两个点[-1, 0]和[0, 1]，k的值为2，如果用map的话，只会得到1 对你的情况，因为键（在本例中为 sqrt(1)）对于两个点都是相同的。因此，您需要使用 multimap，您可以多次使用相同的密钥。阅读 here.

基于您的代码的工作代码示例：

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 here.

什么导致堆栈缓冲区溢出？

What is causing the Stack Buffer Overflow?

arrays

stl

c++11