这个是力扣上面的一道题：点击此处跳转
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。
示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。
注意:
给定数字的范围是 [0, 108]
来源：力扣（LeetCode）
我会附上对官方给出了两种解答的理解，还有我自己的解答，重点写对贪心算法的理解。
- 暴力法
- 贪心算法
- 第三种解法（非官方）
方法一：暴力法
数字最多只有 8 位，因此只有 28 个可用的互换。
算法：
我们将数字存储为长度为 len(num) 的列表。对于位置为 (i, j) 的每个候选交换，我们交换数字并记录组成的新数字是否大于当前答案，然后交换回来恢复原始数字。
唯一的细节可能是检查我们没有引入前导零。我们实际上不需要检查它，因为我们的原始数据没有。
Java
public class Solution {
public int maximumSwap(int num) {
String s = String.valueOf(num);
int len = s.length();
char[] charArray = s.toCharArray();
int max = num;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
swap(charArray, i, j);//交换数字
max = Math.max(max, Integer.parseInt(new String(charArray)));//记录组成新数字是否大于当前答案
swap(charArray, i, j);//交换回来恢复原始数字
}
}
return max;
}
private void swap(char[] charArray, int index1, int index2) {
char temp = charArray[index1];
charArray[index1] = charArray[index2];
charArray[index2] = temp;
}
}
复杂度分析
时间复杂度：O(N^3)其中 NN= 是输入数字的总位数。对于每对数字，我们最多花费 O(N) 的时间来比较最后的序列。
空间复杂度：O(N)，存储在 A 中的信息。
来源：力扣（LeetCode）
例如有数 2746，max=2746
第一层外层循环（拿2依次与7、4、6作比较，得到最大的max值）
拿2与7作交换，得到数7246，与max作比较取最大值赋值给max,max=7246
拿2与4作交换，得到数4726，与max作比较取最大值赋值给max,max=7246
…
第二层外层循环（拿7依次与4、6作比较，得到最大的max值）
第三层外层循环（拿4与6作比较，得到最大的max值）
循环结束，得到最大的max值是7246，将其返回。
```java
方法二：贪心算法
算法：
我们将计算 last[d] = i，最后一次出现的数字d（如果存在）的索引i。
然后，从左到右扫描数字时，如果将来有较大的数字，我们将用最大的数字交换；如果有多个这样的数字，我们将用最开始遇到的数字交换。
public class Solution {
public int maximumSwap(int num) {
String s = String.valueOf(num);
int len = s.length();
char[] charArray = s.toCharArray();
// 记录每个数字出现的最后一次出现的下标
int[] last = new int[10];
for (int i = 0; i < len; i++) {
last[charArray[i] - '0'] = i;
}
// 从左向右扫描，找到当前位置右边的最大的数字并交换
for (int i = 0; i < len - 1; i++) {
// 找最大，所以倒着找
for (int d = 9; d > charArray[i] - '0'; d--) {
if (last[d] > i) {
swap(charArray, i, last[d]);
// 只允许交换一次，因此直接返回
return Integer.parseInt(new String(charArray));
}
}
}
return num;
}
private void swap(char[] charArray, int index1, int index2) {
char temp = charArray[index1];
charArray[index1] = charArray[index2];
charArray[index2] = temp;
}
}
复杂度分析
时间复杂度：O(N)。其中，N 是输入数字的总位数。每个数字最多只考虑一次。
空间复杂度：O(1))，last 使用的额外空间最多只有 10 个。
来源：力扣（LeetCode）
建立last数组（因为一个数字每位上可以是0~9任意数字，一共十个，所以last数组长度设为10）。
last数组存储每个数字出现的最后一次出现的下标，例如数字7897886中，将其转换为数组，数字“8”最后一次出现的下标是5，数字“7”最后一次出现的下标是3
根据last数组，我们可以轻易知道每一个数字在数组中出现的最后一次的下标，
last[9]表示：数字9最后一次出现在数组下标为2的位置，chars[2]
last[8]表示：数字8最后一次出现在数组下标为5的位置，chars[5]
…
将两者比较大小，last[9]表示：数字9最后一次出现在数组下标为2的位置，chars[2]，9大于7，所以交换位置，得到结果。
方法三：个人理解（非官方）
class Solution {
public int maximumSwap(int num) {
char[] chars=String.valueOf(num).toCharArray();
char[] chars2=String.valueOf(num).toCharArray();
for(int i=0;i<chars.length;i++){
for(int j=0;j<chars.length-1-i;j++){
if(chars2[j]<chars2[j+1]){
char k=chars2[j];
chars2[j]=chars2[j+1];
chars2[j+1]=k;}
}
}
int a=0,c=0,flag=0;
for(int i=0;i<chars.length;i++){
if(chars[i]<chars2[i]) {
a=chars2[i];
c=i;
flag=1;
break;
}}
for(int i=chars.length-1;i>=0;i--){
if(chars[i]==a&&flag==1){
char k=chars[i];
chars[i]=chars[c];
chars[c]=k;}
}
return Integer.parseInt(new String(chars));
}}
写两个数组，一个chars存储数字，一下chars2存储排序后的数组(这里使用的冒泡排序，冒泡忘的差不多了哈，见谅)。
例如chars:{2,6,9,8} 那么chars2:{9,8,6,2}
将其用冒泡排序，从大到小进行排序。
两个数组一起遍历，依次进行比较。当chars2[i]>chars[i]时，存储此时的最大值a以及下标c。同时设置了一个flag做标志，flag改变，并退出循环。
接着依次遍历chars，从右到左开始遍历，当满足条件（flag改变 并且 元素与a存储值相等时），交换元素。
个人比较粗心哈，如果有错误欢迎指正！