LeetCode670. Maximum Swap

桃扇骨 2022-06-07 10:16 158阅读 0赞

# Brute-force Solution #

The question specifies that the upperbound of the number is `10^8`, thus the total number of digits in the number is at most 8. Hence the total number of possible swaps is `C[8, 2] = 28`. It is so small that we could actually do a Brute-force solution. That is, we generate every possible number and choose the one with the greatest value.

Suppose `n` is the number of digits in the input number, this algorithm runs in `O(n^3)` time since we need extra `O(n)` time to compare numbers in our algorithm. Space complexity is `O(n)` since we use a length-n char array to store the input number.

Implementation is showed as following:

class Solution {
        public int maximumSwap(int num) {
            char[] digits = String.valueOf(num).toCharArray();
            char[] ret = Arrays.copyOf(digits, digits.length);
    
            for (int i = 0; i < digits.length; i++) {
                for (int j = i + 1; j < digits.length; j++) {
                    char tmp = digits[i];
                    digits[i] = digits[j];
                    digits[j] = tmp;
                    for (int k = 0; k < digits.length; k++) {
                        if (digits[k] != ret[k]) {
                            if (digits[k] > ret[k]) {
                                ret = Arrays.copyOf(digits, digits.length);
                            }
                            break;
                        }
                    }
                    digits[j] = digits[i];
                    digits[i] = tmp;
                }
            }
    
            return Integer.parseInt(new String(ret));
        }
    }

# Greedy Search Solution #

To get the greatest number possible, we need to try to put the greatest possible digit at the leftmost possible position. Since we are only allowed to swap once, so we don’t have to care about remaining digits. All we need to do is find this greatest swap-able digit. Thus we can search from left to right in the original number, and if there is a larger digit appears latter, then we know we can swap it. And we also have to make sure that if there is multiple possible digit that is swapable, we need to swap with the last one to make sure we get the greatest possible number. E.g. for number 27576, the greatest possible number we can get is 77526, which is get by swap “2” with greatest possible number, “7”, at the last occurance of “7”, which is at the 4th position.

The algorithm is described as following:

1.  For each possible digit, i.e. 0~9, find the last appearance of each of them.
2.  Afterwards, search through the digits of the original number from left to right, and then we swap the largest possible digit occurs after it. This digit can be tell from the last-occurance of each digit array generated in previous step.
3.  As soon as we find a dight swapable, it’s done.

This algorithm runs in `O(n)` time where `n` is the number of digits in the number. Space complexity is `O(n)` since we only uses a length-n char array to store input number.

Implementation in Java:

class Solution {
        public int maximumSwap(int num) {
            char[] digits = String.valueOf(num).toCharArray();
    
            // Find the last appearance of each digits
            int[] last = new int[10];
            for (int i = 0; i < digits.length; i++) {
                last[digits[i] - '0'] = i;
            }
    
            // Find the first digit that has another digit after it with a greater value
            for (int i = 0; i < digits.length; i++) {
                for (int j = 9; j > digits[i] - '0'; j--) {
                    if (last[j] > i) {
                        char tmp = digits[i];
                        digits[i] = digits[last[j]];
                        digits[last[j]] = tmp;
                        return Integer.parseInt(new String(digits));
                    }
                }
            }
    
            return num;
        }
    }