向量排序的向量比较函数导致问题[leetcode]

Question

我需要按每个元素向量的第一个元素对向量的向量进行排序。它用于 Leetcode 中的 merge intervals 问题。
我针对这个问题写了下面的代码：

class Solution {
public:
    static bool comparison(const vector<int>& v1, const vector<int>& v2){
        if(v1[0]==v2[0])
            return v1[1]<=v2[1];
        else
            return v1[0]<v2[0];
    }
    
    
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), comparison);
        int n = intervals.size();
        
        vector<vector<int>> res;
        if(n >= 1)
            res.push_back(intervals[0]);
        
        for(int i=0;i<n;i++){
            vector<int> rv = res.back();
            vector<int> iv = intervals[i];
            if(rv[1] >= iv[0]){
                res.pop_back();
                res.push_back({min(rv[0], iv[0]), max(iv[1], rv[1])});
            }
            else{
                res.push_back(iv);
            }
        }
        return res;
    }
};

我在比较函数中尝试做的是，如果向量元素的第一个元素相同，我将使用第二个元素进行排序。此代码仅针对一个测试用例给出运行时错误 （运行时错误：引用绑定到 'const int' 类型的空指针（stl_vector.h））。如果我将比较函数更改为以下内容，它适用于所有测试用例：

static bool comparison(const vector<int>& v1, const vector<int>& v2){
        return v1[0]<v2[0];
}

谁能解释一下原因吗？

Answer 1

std::vector::operator[] 不执行边界检查。由于您不检查向量的大小，因此当您放入空向量时，comparison() 会导致未定义的行为。

通过更改 comparison() 的行为，您也可能会更改排序的行为，这可能会导致传入空向量或不传入空向量。尽管如此，您的运算符还是坏了。

Answer 2

比较器需要满足命名要求 Compare，这需要严格的弱排序。您必须满足的一个条件是：

For all a, comp(a,a) == false

但是举个例子

comparison({0, 0}, {0, 0});

产量true。由于您的比较器不满足所有要求，因此您会出现未定义的行为，这在您的案例中表现为崩溃。

要恢复严格的弱排序，请将 <= 替换为 <:

static bool comparison(const vector<int>& v1, const vector<int>& v2){
    if(v1[0]==v2[0])
        return v1[1] < v2[1];
    else
        return v1[0] < v2[0];
}

您还应该先检查向量的长度，否则有越界访问的风险。

Answer 3

我认为我们不需要在 std::sort 中进行比较，因为它已经根据间隔的开始进行了排序。如果你删除你的算法就可以正常工作：

struct Solution {
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();

        vector<vector<int>> res;

        if (n >= 1) {
            res.push_back(intervals[0]);
        }

        for (int i = 0; i < n; i++) {
            vector<int> rv = res.back();
            vector<int> iv = intervals[i];

            if (rv[1] >= iv[0]) {
                res.pop_back();
                res.push_back({min(rv[0], iv[0]), max(iv[1], rv[1])});

            } else {
                res.push_back(iv);
            }
        }

        return res;
    }
};

更常规一点：

#include <vector>
#include <algorithm>
#include <cstdint>

struct Solution {
    static std::vector<std::vector<int>> merge( std::vector<std::vector<int>> &intervals) {
        if (intervals.size() < 2) {
            return intervals;
        }

        std::sort(std::begin(intervals), std::end(intervals));

        std::vector<std::vector<int>> merged_intervals;
        merged_intervals.push_back(intervals[0]);

        for (std::size_t index = 1; index < intervals.size(); index++) {
            if (merged_intervals.back()[1] >= intervals[index][0]) {
                merged_intervals.back()[1] = std::max(merged_intervals.back()[1], intervals[index][1]);

            } else {
                merged_intervals.push_back(intervals[index]);
            }
        }

        return merged_intervals;
    }
};

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

向量排序的向量比较函数导致问题[leetcode]

comparison function causing problem in vector of vector sorting[leetcode]

c++

runtime-error

comparator

参考资料