Home > OS >  Sort an array by increasing frequency
Sort an array by increasing frequency

Time:10-23

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

Code fiddle

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:

  1. nums[i] is between -100 and 100. The vector v can't handle this case. This could be fixed easily with an offset of 100.

  2. vector<pair<int,int>> v(n);. Remember, this is a vector of frequency. It can't handle case like, for example, n = 5 but num[i] reach 50 or 100. 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.

  • Related