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]
Idea 1. To get a biggest digit for each position, the digit need to swap with the biggest in the number, since it aims to get the maximum valued number, the digit (digits[i]) need to swap with the biggest digit on the right(digits[j] > digits[i], j > i), the digit needs to be the leftmost one which has a bigger digit on the right side. Since needs index to swap, build the maxIndex array. 从右往左建一个maxIndexArray, 再从左到右遍历 找到第一个digits[i] < digits[maxIndex[i]], swap(i, maxIndex[i]).
Note: right most maxIndex, if there are duplicates like 27736, 77236 > 72736
Time complexity: O(n) 2 scan, if string construction is O(n)
Space complexity: O(n)
class Solution {
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int[] maxIndex = new int[digits.length];
maxIndex[digits.length-1] = digits.length-1;
for(int i = digits.length-2; i >=0; --i) {
maxIndex[i] = i;
if(digits[maxIndex[i]] - '0' <= digits[maxIndex[i+1]] - '0') {
maxIndex[i] = maxIndex[i+1];
}
}
for(int i = 0; i < digits.length; ++i) {
if(digits[i] - '0' < digits[maxIndex[i]] - '0') {
char c = digits[i];
digits[i] = digits[maxIndex[i]];
digits[maxIndex[i]] = c;
break;
}
}
return Integer.parseInt(new String(digits));
}
}
Idea 1.a, to avoid maxIndex array, record the maxIndex on the way, 1 scan from right to left
class Solution {
private void swap(char[] digits, int leftIndex, int rightIndex) {
char c = digits[leftIndex];
digits[leftIndex] = digits[rightIndex];
digits[rightIndex] = c;
}
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int leftIndex = -1, rightIndex = -1;
int maxIndex = digits.length-1;
for(int i = digits.length-1; i >=0; --i) {
if(digits[i] > digits[maxIndex]) {
maxIndex = i;
}
else if(digits[i] < digits[maxIndex]) {
leftIndex = i;
rightIndex = maxIndex;
}
}
if(leftIndex == -1) {
return num;
}
swap(digits, leftIndex, rightIndex);
return Integer.parseInt(new String(digits));
}
}
Idea 1.c. Remove the use of toCharArray, convert to digit on the way from right to left.
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public int maximumSwap(int num) {
int leftDigit = -1, rightDigit = -1;
int leftBase = 0, rightBase = 0;
int curr = num;
int maxDigit = -1;
int maxBase = 0;
int base = 1;
while(curr != 0) {
int digit = curr % 10;
if(digit > maxDigit) {
maxDigit = digit;
maxBase = base;
}
else if(digit < maxDigit) {
leftDigit = digit;
leftBase = base;
rightDigit = maxDigit;
rightBase = maxBase;
}
base = base * 10;
curr = curr/10;
}
if(leftDigit == -1) {
return num;
}
num = num - leftDigit*leftBase - rightDigit*rightBase
+ leftDigit* rightBase + rightDigit * leftBase;
return num;
}
}
Idea 2. 官方的妙法，数字只有0-9，建立一个数组记录每个数字出现在最右边的index(从左到右扫), 再从左到右扫，寻找第一个digits[i] < last[d] (d > digits[i] and last[d] > i), swap(digits, i, last[d]).
class Solution {
private void swap(char[] digits, int i, int j) {
char c = digits[i];
digits[i] = digits[j];
digits[j] = c;
}
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int[] last = new int[10];
for(int i = 0; i < digits.length; ++i) {
last[digits[i] - '0'] = i;
}
for(int i = 0; i < digits.length; ++i) {
for(int d = 9; d > digits[i] - '0'; --d) {
if(last[d] > i) {
swap(digits, i, last[d]);
return Integer.valueOf(new String(digits));
}
}
}
return num;
}
}
Idea 3. 虽然也感觉和LT31 Next Permutation有相似的，没有找出规律，网上看到的妙法，从左到右找到第一个valley, 继续valley后找到最大值作为要交换的rightIndex, 然后再从左到右找一个小于最大值的作为leftIndex, swap(digits, leftIndex, rightIndex); LT31是从右到左找第一个peak, peak的左边是rightIndex, 再从右到左找第一个比digits[rightIndex]小的作为leftIndex, 最后交换就是了.
Note. duplicates, rightMost index like 27736, 77236 > 72736, 又犯了错，下次记住这个test case啊
class Solution {
private void swap(char[] digits, int i, int j) {
char c = digits[i];
digits[i] = digits[j];
digits[j] = c;
}
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int rightIndex = 1;
while(rightIndex < digits.length && digits[rightIndex-1] >= digits[rightIndex]) {
++rightIndex;
}
if(rightIndex == digits.length) {
return num;
}
for(int i = rightIndex+1; i < digits.length; ++i) {
if(digits[i] >= digits[rightIndex]) {
rightIndex = i;
}
}
for(int i = 0; i < digits.length; ++i) {
if(digits[i] < digits[rightIndex]) {
swap(digits, i, rightIndex);
break;
}
}
return Integer.parseInt(new String(digits));
}
}