C++ O(n) solution using map [3ms Accepted]


  • 0
    class Solution {
    public:
        int maximumSwap(int num) {
            // calculate the pow vector since the range is [0, 10^8]
            vector<int> pow(9, 1);
            for (int i = 1; i < 9; ++i) pow[i] = pow[i-1] * 10;
            // keep record of the first(right) and last(left) places where 0-9 appear O(n)
            unordered_map<int, pair<int, int> > m;
            for (int i = 0, n = num; n > 0; n = num / pow[++i]) {
                n %= 10;
                if (m.count(n)) m[n].second = i;
                else m[n] = {i, i};
            }
            // swap the bigger one in the first place with the smaller one in the last place O(10*10)
            int result = num;
            for (int i = 9; i >= 0; --i) {
                if (m.count(i)) {
                    int pos = m[i].first, v = i;
                    for (int j = 0; j < i; ++j) {
                        if (m.count(j) && m[j].second > pos) {
                            pos = m[j].second;
                            v = j;
                        }
                    }
                    result = max(result, num + (v - i) * pow[m[i].first] + (i - v) * pow[pos]);
                }            
            }
            return result;
        }
    };
    

Log in to reply
 

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