最大交换

题目描述

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

code

// 每一位数字应该不小于所有排它后面的数字，否则找最大的且排最后面的数字与之交换
class Solution {
    public int maximumSwap(int num) {
        int[] index = new int[10];
        char[] n = String.valueOf(num).toCharArray();

        // 预处理出每个数字最后一次出现的下标
        for (int i = 0; i < n.length; i++)
            index[n[i] - '0'] = i;

        // 将大的数字放到左边
        for (int i = 0; i < n.length; i++) {
            // 从大的数字开始枚举
            for (int j = 9; j > n[i] - '0'; j--) { // 要求数字比当前数字大
                if (index[j] > i) { // 要求下标在当前的右边
                    swap(n, i, index[j]);
                    return Integer.valueOf(String.valueOf(n));
                }
            }
        }
        return num;
    }

    void swap(char[] num, int i, int j) {
        char tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
}