一、题目
给定一个非负整数，你 至多 可以交换一次数字中的任意两位。返回你能得到的最大值。
二、示例
2.1> 示例 1 :
【输入】 2736
【输出】 7236
【解释】 交换数字2和数字7。
2.2> 示例 2 :
【输入】 9973
【输出】 9973
【解释】 不需要交换。
注意:
给定数字的范围是 [0, 10^8]
三、解题思路
3.1> 思路1：排序 + 对比交换
根据题意描述，我们要交换两个数，使其交换后得到最大值。那么从高位开始，找到第一个没按照降序排列的数，就是我们需要替换的数了。所以，我们可以通过Arrays.sort(...)方法，将原有数组进行排序（默认是升序排序，当与原数组对比的时候，我们可以采用对排序后的数组执行倒序遍历即可）。
如下图所示：将原数组与排序数组进行对比，发现第3个位置是不对的，应该是8，但是原数组却是3，所以我们将原数组的3替换为8。
那么，下一步，就是需要将原数组的8替换为3了。此时，为了保证交互后得到最大值，所以我们需要采用逆序遍历的方式，从数组的尾部开始找8，当找到后，将8替换为3即可。
3.2> 思路2：倒序遍历最大下标 + 对比交换
在思路2中，我们首先创建一个数组maxIndexs，它是用来存放数组下标index用的。那存放什么index呢？就是说，我们逆序遍历数组numArr，将当前遍历过的数组元素中，最大值的下标index存入到相应的maxIndexs中。如下图所示：
- 遍历
numArr[8]，当前最大值就是它本身（下标index=8），所以maxIndexs[8]被赋值8；- 遍历
numArr[7]，当前最大值就是它本身（下标index=7），所以maxIndexs[7]被赋值7；- 遍历
numArr[6]，当前最大值就是它本身（下标index=6），所以maxIndexs[6]被赋值6；- ... ...
从上图中我们可以发现一个规律，就是在已经降序排序好的数组中，maxIndexs中存储的也就是numArr中该元素自身的下标，也就是说，每个元素在判断最大值的时候，都是与它右侧的所有元素进行对比的。那么，根据这个规律，我们再来尝试解答本题。
如下图所示，numArr逆序遍历后，maxIndexs=[0,4,4,4,4,5]，那么我们从头开始对比 numArr[i] 和 numArr[maxIndexs[i]] 的值，如果发现不同了，那么互换的下标就是 i 和 maxIndexs[i] 。
四、代码实现
4.1> 代码1：排序 + 对比
class Solution {
public int maximumSwap(int num) {
char[] num1 = String.valueOf(num).toCharArray();
char[] num2 = String.valueOf(num).toCharArray();
Arrays.sort(num2);
Character lc = null, hc = null;
for (int i = 0; i < num1.length; i++) {
if (num1[i] != num2[num1.length - i - 1]) {
lc = num1[i];
hc = num2[num1.length - i - 1];
num1[i] = num2[num1.length - i - 1];
break;
}
}
if (lc != null) {
for (int i = num1.length - 1; i >= 0; i--) {
if (hc.equals(num1[i])) {
num1[i] = lc;
break;
}
}
}
return Integer.valueOf(new String(num1));
}
}
4.2> 代码2：倒序遍历最大下标 + 对比
class Solution {
public int maximumSwap(int num) {
char[] numArr = String.valueOf(num).toCharArray();
int[] maxIndexs = new int[numArr.length];
int index = numArr.length - 1;
for (int i = numArr.length - 1; i >= 0; i--) {
if (numArr[i] > numArr[index]) index = i;
maxIndexs[i] = index;
}
for (int i = 0; i < numArr.length; i++) {
if (numArr[i] != numArr[maxIndexs[i]]) {
char temp = numArr[i];
numArr[i] = numArr[maxIndexs[i]];
numArr[maxIndexs[i]] = temp;
break;
}
}
return Integer.valueOf(new String(numArr));
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」