题目描述

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

示例

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

题目解析

  1. 维护一个长度为10的数组,存储每位元素最后一次出现的位置
  2. 遍历0 - n-1位置处的元素,用其和9-1之间的数比较
    1. 如果比当前数的数出现的位置在当前数后面就交换
  3. 因为只能交换一次所以只需要找到后面出现的最大数交换即可

Coding

class Solution {
public int maximumSwap(int num) {
int[] latest = new int[10];
//记录每个数字最后出现的位置
String strNum = String.valueOf(num);
char[] arr = strNum.toCharArray();
int n = arr.length;
for(int i = 0;i < n;i++){
latest[arr[i] - '0'] = i;
}

for(int i = 0;i < n - 1;i++){
for(int j = 9;j > arr[i] - '0';j--){
if(latest[j] > i){
exch(arr,latest[j],i);
return Integer.parseInt(new String(arr));
}
}
}
return num;
}
public void exch(char[] arr,int index1,int index2){
char tem = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tem;
}
}