气球射箭问题代码报错：对空指针应用非零偏移4

题目描述 #

在代表XY平面的平面墙上贴有若干球形气球，气球用二维整数数组points表示，points[i] = [xstart, xend]表示气球的水平直径介于xstart和xend之间，未知气球的精确y坐标。
可沿x轴不同点垂直向上（y轴正方向）射箭，若x满足xstart ≤ x ≤ xend，则该位置射出的箭会戳破对应气球，箭可无限向上飞行，戳破路径上所有气球。给定points数组，返回戳破所有气球所需的最少箭数。

原代码实现 #

bool compare(vector<int> &a,vector<int> &b){
          return a[1]<=b[1];
}
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==1) return 1;
        sort(points.begin(),points.end(),compare);
        int arrows=1,end=points[0][1];
        for(int i=1;i<points.size();i++){
            if(points[i][0]>end){
                arrows++;
                end=points[i][1];
            }
        }
        return arrows;
    }
};

运行时错误信息 #

Line 1034: Char 34: runtime error: applying non-zero offset 4 to null pointer (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

错误原因 #

代码未处理points为空数组的边界情况：当输入数组长度为0时，程序跳过size()==1的判断后，直接执行sort并访问points[0][1]，此时points[0]是空指针，对空指针进行偏移操作触发了运行时错误。

修复方案 #

在函数开头优先处理空数组的情况，同时优化排序比较逻辑以符合STL排序的严格弱序要求：

class Solution {
public:
    static bool compare(const vector<int> &a, const vector<int> &b){
        return a[1] < b[1];
    }
    
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty()) return 0;
        if(points.size() == 1) return 1;
        
        sort(points.begin(), points.end(), compare);
        int arrows = 1;
        int end = points[0][1];
        
        for(int i = 1; i < points.size(); i++){
            if(points[i][0] > end){
                arrows++;
                end = points[i][1];
            }
        }
        return arrows;
    }
};

优化说明 #

• 将比较函数改为类的静态成员函数，避免全局函数的命名冲突问题；
• 把比较条件从a[1]<=b[1]改为a[1]<b[1]，满足STL排序要求的严格弱序规则，避免排序行为异常。

内容的提问来源于stack exchange，提问作者Harshit Khurana