给定一个非负整数,你可以至多交换一次数字中的任意两位,返回你得到的最大值。 java
时间: 2024-06-01 12:13:26 浏览: 189
好的,这是一个非常好的问题。这个问题的解法比较简单,我们可以使用贪心算法来解决它。
具体来说,我们可以将这个非负整数转化为字符串,然后逐一比较相邻的字符,如果前面的字符比后面的字符小,那么就交换它们,然后再将整个字符串转化为整数。这样做的原理是,我们通过交换数字可以让高位上的数字变大,从而得到更大的整数。
下面是一个基于贪心算法的 Java 代码实现:
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int[] last = new int[10];
for (int i = 0; i < digits.length; i++) {
last[digits[i] - '0'] = i;
}
for (int i = 0; i < digits.length; i++) {
for (int j = 9; j > digits[i] - '0'; j--) {
if (last[j] > i) {
char tmp = digits[i];
digits[i] = digits[last[j]];
digits[last[j]] = tmp;
return Integer.parseInt(new String(digits));
}
}
}
return num;
}
这个算法的时间复杂度是 O(n),其中 n 是这个非负整数的位数。
阅读全文