https://leetcode.com/problems/maximum-swap/description/
X.
char[] A = Integer.toString(num).toCharArray();
int[] last = new int[10]; //
for (int i = 0; i < A.length; i++) {
last[A[i] - '0'] = i;
}
for (int i = 0; i < A.length; i++) {
for (int d = 9; d > A[i] - '0'; d--) {
if (last[d] > i) {
char tmp = A[i];
A[i] = A[last[d]];
A[last[d]] = tmp;
return Integer.valueOf(new String(A));
}
}
}
return num;
}
https://leetcode.com/problems/maximum-swap/discuss/107068/Java-simple-solution-O(n)-time
X.
char[] A = Integer.toString(num).toCharArray();
char[] ans = Arrays.copyOf(A, A.length);
for (int i = 0; i < A.length; i++) {
for (int j = i+1; j < A.length; j++) {
char tmp = A[i];
A[i] = A[j];
A[j] = tmp;
for (int k = 0; k < A.length; k++){
if (A[k] != ans[k]){
if (A[k] > ans[k]) {
ans = Arrays.copyOf(A, A.length);
}
break;
}
}
A[j] = A[i];
A[i] = tmp;
}
}
return Integer.valueOf(new String(ans));
}
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]
At each digit of the input number in order, if there is a larger digit that occurs later, we know that the best swap must occur with the digit we are currently considering.
Algorithm
We will compute , the index of the last occurrence of digit (if it exists).
Afterwards, when scanning the number from left to right, if there is a larger digit in the future, we will swap it with the largest such digit; if there are multiple such digits, we will swap it with the one that occurs the latest.
public int maximumSwap(int num) {char[] A = Integer.toString(num).toCharArray();
int[] last = new int[10]; //
for (int i = 0; i < A.length; i++) {
last[A[i] - '0'] = i;
}
for (int i = 0; i < A.length; i++) {
for (int d = 9; d > A[i] - '0'; d--) {
if (last[d] > i) {
char tmp = A[i];
A[i] = A[last[d]];
A[last[d]] = tmp;
return Integer.valueOf(new String(A));
}
}
}
return num;
}
https://leetcode.com/problems/maximum-swap/discuss/107068/Java-simple-solution-O(n)-time
public int maximumSwap(int num) {
char[] nums = String.valueOf(num).toCharArray();
// 332()49 return
Optional<Integer> incPos = findFirstIncreasingPos(nums);
if (!incPos.isPresent()) {
// 321
return num;
}
int maxPos = findMaxPosition(nums, incPos.get());
int firstLesserPos = findFirstLesserPos(nums, incPos.get(), nums[maxPos]);
swap(nums, firstLesserPos, maxPos);
return Integer.parseInt(String.valueOf(nums));
}
// not including end
private int findFirstLesserPos(char[] nums, int end, char ch) {
for (int i = 0; i < end; i++) {
if (nums[i] < ch) { // not >
return i;
}
}
throw new RuntimeException("should never happen");
}
private void swap(char[] nums, int i, int j) {
char tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
// precondition: size >1
// 1234 return pos:1
private Optional<Integer> findFirstIncreasingPos(char[] nums) {
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1])
return Optional.of(i);
}
return Optional.empty();
}
// precondition: must exist
// 32123()
private int findMaxPosition(char[] nums, int start) {
int maxPos = start;
for (int i = start; i < nums.length; i++) {
if (nums[i] >= nums[maxPos]) {
maxPos = i;
}
}
return maxPos;
}
https://leetcode.com/problems/maximum-swap/discuss/120360/O(n)-time-and-O(1)-space-without-using-array
I am visualizing this problem as a monotonic line from right to left with dips. So, I am traversing the number from right to left.
Objective 1- To find the number just before the dip with Max possible value. I am recording it as max and its index as maxI.
Objective 1- To find the number just before the dip with Max possible value. I am recording it as max and its index as maxI.
Objective 2 - To find a dip which is farthest from right. I am recording it as min and its index as minI.
If I find a dip, I am updating the max value. If there is a smaller value after the max value, then I am updating the min. Whenever there is an update in min and max, I record their Indexes and use them at the time of recreating the number.
public int maximumSwap(int num) {
int numC = num;
int min = Integer.MAX_VALUE;
int minI = -1;
int max = Integer.MIN_VALUE;
int maxI = -1;
int pre = -1;
int i = 0;
int lmax = Integer.MIN_VALUE;
int lmaxI = -1;
//find out min and max values and their index in the num
while(num != 0){
int cur = num % 10;
num = num / 10;
//record increase in max value locally
if(cur > lmax){
lmax = cur;
lmaxI = i +1 ;
}
//record if there is a dip
if(cur < pre && max < lmax){
max = lmax;
maxI = lmaxI;
}
//record min value
if(cur < max && minI < i+1){
min = cur;
minI = i + 1;
}
i++;
pre = cur;
}
int result = 0;
// re-create that number by swaping min and max
while(i != 0){
if(i == maxI){
result = result + (min * (int)(Math.pow(10,i-1)));
}
else if(i == minI){
result = result + (max * (int)(Math.pow(10,i-1)));
}
else result = result + ((numC / (int)(Math.pow(10,i -1 ))) * (int)(Math.pow(10,i-1)));
numC = numC % (int)(Math.pow(10,i-1)) ;
i--;
}
return result;
}X.
- Time Complexity: , where is the total number of digits in the input number. For each pair of digits, we spend up to time to compare the final sequences.
- Space Complexity: , the information stored in .
char[] A = Integer.toString(num).toCharArray();
char[] ans = Arrays.copyOf(A, A.length);
for (int i = 0; i < A.length; i++) {
for (int j = i+1; j < A.length; j++) {
char tmp = A[i];
A[i] = A[j];
A[j] = tmp;
for (int k = 0; k < A.length; k++){
if (A[k] != ans[k]){
if (A[k] > ans[k]) {
ans = Arrays.copyOf(A, A.length);
}
break;
}
}
A[j] = A[i];
A[i] = tmp;
}
}
return Integer.valueOf(new String(ans));
}
