Maximum Swap

Question

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.

LeetCodeleetcode.com/problems/maximum-swap

Solution

/*
@param: int
@return: int
Algorithm: Bruteforce 数据两不大，可解O(n^2);
Greedy: 记录每一个数位最大的index，然后从头遍历，如果发现后面有比当前数字大的交换并return。
tips: 数字转array以及array转数字
*/
public int maximumSwap(int num) {
    char[] digit = Integer.toString(num).toCharArray();
    
    int[] pos = new int[10];
    for (int i = 0; i < digit.length; i++) 
        pos[digit[i]-'0'] = i;
    
    for (int i = 0; i < digit.length; i++) 
        for (int j = 9; j > digit[i]-'0'; j--) {
            if (pos[j] > i) {
                char tmp = digit[i];
                digit[i] = (char)(j+'0');
                digit[pos[j]] = tmp;
                return Integer.valueOf(new String(digit));
            }
        }
    return num;
}