C++

Forum

 
About the upper_bound Function

t im (45)
Edit: In Solution 2, if I use upper_bound function instead of the menber function of multiset, time limit exceeded will alse be reported. So, I think the difference if upper_bound function and the member function upper_bound of multiset results in the situation. In that case, where is the difference between the two functions.
-------------------------------------------------------------------------------------------------------

Previous question:
When I solve the #870 of leetcode(https://leetcode.com/problems/advantage-shuffle/), I meet with a question about the upper_bound function.
The question is to rearrange nums1 to make the total number of i satisfying nums1[i] > nums2[i] as large as possible.
Here is my code using list:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
// Solution 1
// sort nums1 first and save it in list for fast delete, then find the first  
// element that is greater than nums2[i] and delete it in the list. If not find, 
// using the head of list and delete it.
vector<int> Solution::advantageCount(vector<int>& nums1, vector<int>& nums2)
{
    sort(nums1.begin(), nums1.end());
    list<int> tmp(nums1.begin(), nums1.end());
    for (int i = 0; i < nums2.size(); ++i)
    {
        auto it = upper_bound(tmp.begin(), tmp.end(), nums2[i]);
        if (it == tmp.end())
        {
            nums1[i] = tmp.front();
            tmp.erase(tmp.begin());
        }
        else
        {
            nums1[i] = *it;
            tmp.erase(it);
        }
    }
    return nums1;
}

Code using multiset is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
// Solution 2
vector<int> advantageCount(vector<int>& a, vector<int>& b) {
    multiset<int> s;
    vector<int> v;
    for (int i = 0; i < a.size(); i++) {
        s.insert(a[i]);
    }
    for (int i = 0; i < b.size(); i++) {
        // auto it = upper_bound(s.begin(), s.end(), b[i]); result in TLE
        auto it = s.upper_bound(b[i]);
        if (it != s.end()) {
            v.push_back(*(it));
            s.erase(it);
        }
        else {
            v.push_back(*(s.begin()));
            s.erase(s.begin());
        }
    }
    return v;
}

I think the two solutions are different in the container that saves the sorted nums2. However, solution 1 reports time limit exceeded while solution 2 accepted. I doubt it results from the upper_bound function.
By the way, what will happen if the container input to unpper_bound is not sorted?
Thanks very much if you can help me.

Last edited on
helios (17574)
It's unclear to me why solution 1 would be accepted but solution 2 rejected. std::upper_bound() on a linked list takes linear time, so solution 1 takes quadratic time, while solution 2 takes only linearithmic time. I can only guess that erasing the first element from an std::multiset has a very high constant cost.

By the way, here's my solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
class Solution {
public:
    template <typename T>
    static bool compare(const T &x, const T &y){
        return x.first < y.first;
    }
    vector<int> advantageCount(vector<int> &a, vector<int> &b) {
        if (!a.size())
            return a;
        
        vector<pair<int, bool>> copyA;
        copyA.reserve(a.size());
        for (auto i : a)
            copyA.emplace_back(i, false);
        sort(copyA.begin(), copyA.end(), compare<pair<int, bool>>);
        
        typedef pair<int, size_t> P;
        vector<P> copyB;
        copyB.reserve(b.size());
        {
            size_t j = 0;
            for (auto i : b)
                copyB.emplace_back(i, j++);
        }
        sort(copyB.begin(), copyB.end(), compare<P>);
        
        size_t n = 0;
        size_t j = 0;
        for (size_t i = 0; i < a.size() && j < a.size(); i++, j++){
            if (copyA[j].first <= copyB[i].first){
                auto b = copyA.begin();
                auto e = copyA.end();
                auto it = upper_bound(
                    b + j,
                    e,
                    make_pair(copyB[i].first, false),
                    compare<P>
                );
                if (it == e)
                    break;
                j = it - b;
            }
            copyA[j].second = true;
            a[copyB[n++].second] = copyA[j].first;
        }
        for (auto &i : copyA)
            if (!i.second)
                a[copyB[n++].second] = i.first;
        return a;
    }
};
JLBorges (13770)
> where is the difference between the two functions.

std::upper_bound

The number of comparisons performed is logarithmic in the distance between first and last (At most log 2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear. Notably, std::set and std::multiset iterators are not random access, and so their member functions std::set::upper_bound (resp. std::multiset::upper_bound) should be preferred.
https://en.cppreference.com/w/cpp/algorithm/upper_bound

The member functions have logarithmic complexity.


> what will happen if the container input to upper_bound is not sorted?

The range need not be a fully sorted range; it can be a suitably partitioned one.

The range [first, last) must be partitioned with respect to the expression !(value < element) or !comp(value, element), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.
https://en.cppreference.com/w/cpp/algorithm/upper_bound


If it is not partitioned, we would get unpredictable results (technically undefined behaviour).


t im (45)
Thanks for your answers that benefit me.
Topic archived. No new replies allowed.