Java simple solution, O(n) time


  • 51

    Use buckets to record the last position of digit 0 ~ 9 in this num.

    Loop through the num array from left to right. For each position, we check whether there exists a larger digit in this num (start from 9 to current digit). We also need to make sure the position of this larger digit is behind the current one. If we find it, simply swap these two digits and return the result.

    class Solution {
        public int maximumSwap(int num) {
            char[] digits = Integer.toString(num).toCharArray();
            
            int[] buckets = new int[10];
            for (int i = 0; i < digits.length; i++) {
                buckets[digits[i] - '0'] = i;
            }
            
            for (int i = 0; i < digits.length; i++) {
                for (int k = 9; k > digits[i] - '0'; k--) {
                    if (buckets[k] > i) {
                        char tmp = digits[i];
                        digits[i] = digits[buckets[k]];
                        digits[buckets[k]] = tmp;
                        return Integer.valueOf(new String(digits));
                    }
                }
            }
            
            return num;
        }
    }
    

  • 0
    B

    @joeztang What an amazing solution it is!! So brilliant !
    Easy understanding solution. Voted up!


  • 0
    J

    The idea to use buckets to store the last occurrence indices is so damn imaginative!


  • 6
    B

    @joeztang said in Java simple solution, O(n) time:

       for (int i = 0; i < digits.length; i++) {
            for (int k = 9; k > digits[i] - '0'; k--) {
                if (buckets[k] > i) {
                    char tmp = digits[i];
                    digits[i] = digits[buckets[k]];
                    digits[buckets[k]] = tmp;
                    return Integer.valueOf(new String(digits));
                }
            }
        }
    

    This loop can be further optimized. As written it's a 10*n runtime, but the inner loop doesn't need to start from 9 for all digits. With '8745' as an example, when we first consider 8, we've already concluded there's no 9 to its right, so when considering 7, we don't need to check 9 again.

        max = 9
        for (int i = 0; i < digits.length; i++) {
            for (int k = max; k > digits[i] - '0'; k--) {
                if (buckets[k] > i) {
                    char tmp = digits[i];
                    digits[i] = digits[buckets[k]];
                    digits[buckets[k]] = tmp;
                    return Integer.valueOf(new String(digits));
                }
            }
            max = digits[i] - '0';
        }
    

    With this, each number is considered at most once without generating a solution, making the running time 1*n.


  • 2
    D

    A minor improvement as we could infer the update digit from k, so the inner swap logic does not require a tmp variable here:

       for (int i = 0; i < digits.length; i++) {
            for (int k = 9; k > digits[i] - '0'; k--) {
                if (buckets[k] > i) {
                    digits[buckets[k]] = digits[i];
                    digits[i] = (char)(k + '0');
                    return Integer.valueOf(new String(digits));
                }
            }
        }

  • 0

    It's really o(n) time? ,the double for loop is not o (n)time


  • 3
    F

    @CP_UESTC Because the iteration time of the second loop will be at most 9 times which can be regarded as constant time.


  • 0
    C
    This post is deleted!

  • 0
    I

    One pass, no buckets:

            char[] ca = Integer.toString(num).toCharArray();
            int from = -1, to = -1;
            for (int i = 1; i < ca.length; ++i) {
                if (from < 0 && ca[i] > ca[i - 1]) {
                    from = i - 1;
                    to = i;
                }
                for (int j = from - 1; j >= 0 && ca[i] > ca[j]; --j) from = j;
                if (to >= 0 && ca[i] >= ca[to]) to = i;
            }
            if (from >= 0) {
                char tmp = ca[from];
                ca[from] = ca[to];
                ca[to] = tmp;
            }
            return Integer.parseInt(new String(ca));
    

  • 0
    D

    I like this idea, thanks!


  • 0
    R

    Very good idea!


  • 1
    S

    Amazing solution!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.