C++: No next_permutation, No to_string, No sort, No 64-bit integer, only a mulitset!


  • 0

    Well, it is nearly an one-month-old problem, but I just saw it now, and there seems no solution like this. This solution is familiar with next_permutation, but another realization.

    int nextGreaterElement(int n) {
        multiset<int> d;
        while (n) {
            int t = n % 10;
            n /= 10;
            if (d.size() && *d.rbegin() > t) {
                auto it = d.upper_bound(t);
                long long ret = n * 10 + *it;
                d.erase(it);
                d.insert(t);
                for (int i : d) ret = ret * 10 + i;
                return ret > INT_MAX ? -1 : ret;
            }
            d.insert(t);
        }
        return -1;
    }
    

    How about no long long is allowed to judge the overflow in int?
    Last year, when I took part in an internship interview with Microsoft, Suzhou, China,
    I was asked a 'translate a digit string to int' problem. So simple, isn't it?
    But I was asked how to judge the overflow problem of the int type, I answered to use an long long and compare it with INT_MAX, and the interviewer asked how about no long long was allowed? or how about 'translate a digit string to long long'?
    So you should remember that the value of INT_MAX is 2147483647, then you could have this solution:

    int nextGreaterElement(int n) {
        multiset<int> d;
        while (n) {
            int t = n % 10;
            n /= 10;
            if (d.size() && *d.rbegin() > t) {
                auto it = d.upper_bound(t);
                n = n * 10 + *it;
                d.erase(it);
                d.insert(t);
                for (int i : d) {
                    if (n > 214748364 || n == 214748364 && i > 7)
                        return -1;
                    n = n * 10 + i;
                }
                return n;
            }
            d.insert(t);
        }
        return -1;
    }

Log in to reply
 

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