I use set instead of vector to store the data and it time out, why


  • 0
    L

    The code I am using is:
    vector<int> countSmaller(vector<int>& nums) {
    vector<int> result = nums;
    multiset<int> data;
    for (int i = nums.size() - 1; i >= 0; i--) {
    auto it = data.lower_bound(nums[i]);
    int dis = distance(data.begin(), it);
    result[i] = dis;
    data.insert(nums[i]); //It should be log(n), right?
    }
    return result;
    }
    It timed out.

    I updated a little bit by changing the multiset into vector and it worked:
    vector<int> countSmaller(vector<int>& nums) {
    vector<int> result = nums;
    vector<int> data;
    for (int i = nums.size() - 1; i >= 0; i--) {
    auto it = lower_bound(data.begin(), data.end(), nums[i]);
    int dis = distance(data.begin(), it);
    result[i] = dis;
    data.insert(it, nums[i]);
    }
    return result;
    }

    I feel the time complexity for both is supposed to be O(nlogn), but why using set is slower?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.