C++, concise code, O(N = 8)


  • 2
    Z

    This question is very easy. I just want to share an O(N) solution. Here N (<= 8) is the number of digits in num.

    I use pos[i] to represent the index of maximum digit in range [i, N);
    For example,

    N = 8,
    index      0  1  2  3  4  5  6  7       
    num        2  7  3  6  9  3  4  1
    pos        4  4  4  4  4  6  6  7                       
    

    I scan the number to find the first index k, which is not the maximum digit in range [k, N). And swap it with that digit.

    class Solution {
    public:
        int maximumSwap(int num) {
            string s = to_string(num);
            int n = s.size();
            vector<int> pos(n, n-1);
            // the index of maximum digit in range [i, n)
            for (int i = n-2; i >= 0; i--) 
                pos[i] = s[i] > s[pos[i+1]]? i:pos[i+1];
            int i = 0;
            // find the first index whose digit is not maximum, and swap it
            while (i < n && s[i] >= s[pos[i]]) i++;
            if (i < n) swap(s[i], s[pos[i]]);
            return stoi(s);
        }
    };
    

  • 0
    S

    clean solution.


Log in to reply
 

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