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:
- The given number is in the range [0, 108]
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
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;
}
}
}
}