Formatted question description: https://leetcode.ca/all/670.html

670. Maximum Swap (Medium)

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: 9973
Output: 9973
Explanation: No swap.

Note:

1. The given number is in the range [0, 10⁸]

Solution 1.

// OJ: https://leetcode.com/problems/maximum-swap/

// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maximumSwap(int num) {
        string digits = to_string(num), memo(digits.size(), '\0');
        int maxIndex = digits.size() - 1;
        for (int i = digits.size() - 1; i >= 0; --i) {
            if (digits[i] > digits[maxIndex]) maxIndex = i;
            memo[i] = maxIndex;
        }
        for (int i = 0; i < digits.size(); ++i) {
            if (memo[i] > i && digits[i] != digits[memo[i]]) {
                swap(digits[i], digits[memo[i]]);
                return stoi(digits);
            }
        }
        return num;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/maximum-swap/

// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maximumSwap(int num) {
        string digits = to_string(num);
        int last[10] = {};
        for (int i = 0; i < digits.size(); ++i) last[digits[i] - '0'] = i;
        for (int i = 0; i < digits.size(); ++i) {
            for (int j = 9; j > digits[i] - '0'; --j) {
                if (last[j] > i) {
                    swap(digits[i], digits[last[j]]);
                    return stoi(digits);
                }
            }
        }
        return num;
    }
};

Java

• Java
• C++
• Python

• class Solution {
      public int maximumSwap(int num) {
          char[] array = String.valueOf(num).toCharArray();
          selectionSort(array);
          String newNumStr = new String(array);
          int newNum = Integer.parseInt(newNumStr);
          return newNum;
      }
  
      public void selectionSort(char[] array) {
          int length = array.length;
          int lengthOuter = length - 1;
          for (int i = 0; i < lengthOuter; i++) {
              char curDigit = array[i];
              int maxIndex = length - 1;
              char maxDigit = array[length - 1];
              for (int j = length - 1; j > i; j--) {
                  char digit = array[j];
                  if (digit > maxDigit) {
                      maxIndex = j;
                      maxDigit = digit;
                  }
              }
              if (maxDigit > curDigit) {
                  array[i] = maxDigit;
                  array[maxIndex] = curDigit;
                  return;
              }
          }
      }
  }
  

• // OJ: https://leetcode.com/problems/maximum-swap/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int maximumSwap(int num) {
          string digits = to_string(num), memo(digits.size(), '\0');
          int maxIndex = digits.size() - 1;
          for (int i = digits.size() - 1; i >= 0; --i) {
              if (digits[i] > digits[maxIndex]) maxIndex = i;
              memo[i] = maxIndex;
          }
          for (int i = 0; i < digits.size(); ++i) {
              if (memo[i] > i && digits[i] != digits[memo[i]]) {
                  swap(digits[i], digits[memo[i]]);
                  return stoi(digits);
              }
          }
          return num;
      }
  };
  

• print("Todo!")
  

All Problems

All Solutions