C++ one-pass simple & fast solution: 1-3ms, O(n) time


  • 5
    T

    Actually this problem can be easily solved by only one pass from backward. During the scan, we only need to do 2 things:

    1. record the largest digit (maxdigit) and its corresponding index (maxidx);
    2. if the current digit is smaller than the largest digit, this digit and the largest digit are the best candidate for max swap so far. In this case, this digit pair is recorded (leftidx and rightidx).
    
        int maximumSwap(int num) {
            string numstr = std::to_string(num);
    
            int maxidx = -1; int maxdigit = -1;
            int leftidx = -1; int rightidx = -1;        
    
            for (int i = numstr.size() - 1; i >= 0; --i) {
                // current digit is the largest by far
                if (numstr[i] > maxdigit) {
                    maxdigit = numstr[i];
                    maxidx = i;
                    continue;
                }
    
                // best candidate for max swap if there is no more 
                // such situation on the left side
                if (numstr[i] < maxdigit) {
                    leftidx = i;
                    rightidx = maxidx;
                }
            }
    
            // num is already in order
            if (leftidx == -1) return num;
    
            std::swap(numstr[leftidx], numstr[rightidx]);
    
            return std::stoi(numstr);
        }
    

  • 0
    X

    Expressive solutions!


  • 0
    S

    Really like your solution! simple and efficient :)


  • 0
    W

    I really like your solution. you did what required. only one swap!! Great job!! I translate it into python as follows.

        def maximumSwap(self, num):
            """
            :type num: int
            :rtype: int
            """
            num_str = list(str(num))
            max_i, max_n, left, right = -1, -1, -1, -1
            for i in xrange(len(num_str)-1, -1, -1):
                if int(num_str[i]) > int(max_n):
                    max_n = num_str[i]
                    max_i = i
                    continue
                    
                if int(num_str[i]) < int(max_n):
                    left = i
                    right = max_i
    
            if left == -1: return num
            else:
                num_str[left], num_str[right] = num_str[right], num_str[left]
            return int("".join(num_str))
    

  • 0
    T

    @WeiFoo it's my pleasure :), it is great to see you like my solution and translated it to other language, thx


Log in to reply
 

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