Can anyone please explain how to deal with run time error?
Line 1034: Char 34: runtime error: addition of unsigned offset to 0x607000000020 overflowed to 0x607000000018 (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
class Solution {
public:
static bool cmp(pair<int,int> a, pair<int,int> b){
if(a.first<b.first) return true;
if(a.first==b.first && a.second>b.second) return true;
return false;
}
vector<int> frequencySort(vector<int>& nums) {
int n = nums.size();
vector<int> res;
vector<pair<int,int>> v(n);
for(int i = 0;i<n;i ){
v[nums[i]].first ;
v[nums[i]].second = nums[i];
}
sort(v.begin(),v.end(),cmp);
for(int i =0;i<n;i ){
for(int j =0;j<v[i].first;j ){
res.push_back(v[i].second);
}
}
return res;
}
};
CodePudding user response:
There're 2 problems:
nums[i]
is between-100
and100
. The vectorv
can't handle this case. This could be fixed easily with an offset of 100.vector<pair<int,int>> v(n);
. Remember, this is a vector of frequency. It can't handle case like, for example,n = 5
butnum[i]
reach50
or100
. This can also be fixed with a different const resize.
New code:
static bool cmp(pair<int,int> a, pair<int,int> b){
if(a.first<b.first) return true;
if(a.first==b.first && a.second>b.second) return true;
return false;
}
const int offset = 100;
const int sz = 201; //because with an offset of 100, nums[i] could reach max 100 100=200
vector<int> frequencySort(vector<int>& nums)
{
int n = nums.size();
vector<int> res;
vector<pair<int,int>> v(sz);
for(int i = 0;i<n;i ){
v[nums[i] offset].first ;
v[nums[i] offset].second = nums[i] offset;
}
sort(v.begin(),v.end(),cmp);
for(int i =0;i<sz;i ){
for(int j =0;j<v[i].first;j ){
res.push_back(v[i].second-offset);
}
}
return res;
}
P.S: When doing programming problems, you should check the constraint:
1 <= nums.length <= 100
-100 <= nums[i] <= 100
and testcases. In this problem, the case:
Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]
that Leetcode provide could help you debug quicker.