Description
You are given an integer num. You can swap two digits at most once to get the maximum valued number.
Return the maximum valued number you can get.
Example 1:
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: num = 9973
Output: 9973
Explanation: No swap.
Constraints:
Solutions
Solution 1: Greedy Algorithm
First, we convert the number into a string s. Then, we traverse the string s from right to left, using an array or hash table d to record the position of the maximum number to the right of each number (it can be the position of the number itself).
Next, we traverse d from left to right. If s[i] < s[d[i]], we swap them and exit the traversal process.
Finally, we convert the string s back into a number, which is the answer.
The time complexity is O(log M), and the space complexity is O(log M). Here, M is the range of the number num.
PythonJavaC++GoTypeScriptRust
class Solution:
def maximumSwap(self, num: int) -> int:
s = list(str(num))
n = len(s)
d = list(range(n))
for i in range(n - 2, -1, -1):
if s[i] <= s[d[i + 1]]:
d[i] = d[i + 1]
for i, j in enumerate(d):
if s[i] < s[j]:
s[i], s[j] = s[j], s[i]
break
return int(''.join(s))(code-box)
class Solution {
public int maximumSwap(int num) {
char[] s = String.valueOf(num).toCharArray();
int n = s.length;
int[] d = new int[n];
for (int i = 0; i < n; ++i) {
d[i] = i;
}
for (int i = n - 2; i >= 0; --i) {
if (s[i] <= s[d[i + 1]]) {
d[i] = d[i + 1];
}
}
for (int i = 0; i < n; ++i) {
int j = d[i];
if (s[i] < s[j]) {
char t = s[i];
s[i] = s[j];
s[j] = t;
break;
}
}
return Integer.parseInt(String.valueOf(s));
}
}(code-box)
class Solution {
public:
int maximumSwap(int num) {
string s = to_string(num);
int n = s.size();
vector<int> d(n);
iota(d.begin(), d.end(), 0);
for (int i = n - 2; ~i; --i) {
if (s[i] <= s[d[i + 1]]) {
d[i] = d[i + 1];
}
}
for (int i = 0; i < n; ++i) {
int j = d[i];
if (s[i] < s[j]) {
swap(s[i], s[j]);
break;
}
}
return stoi(s);
}
};(code-box)
func maximumSwap(num int) int {
s := []byte(strconv.Itoa(num))
n := len(s)
d := make([]int, n)
for i := range d {
d[i] = i
}
for i := n - 2; i >= 0; i-- {
if s[i] <= s[d[i+1]] {
d[i] = d[i+1]
}
}
for i, j := range d {
if s[i] < s[j] {
s[i], s[j] = s[j], s[i]
break
}
}
ans, _ := strconv.Atoi(string(s))
return ans
}(code-box)
function maximumSwap(num: number): number {
const list = new Array();
while (num !== 0) {
list.push(num % 10);
num = Math.floor(num / 10);
}
const n = list.length;
const idx = new Array();
for (let i = 0, j = 0; i < n; i++) {
if (list[i] > list[j]) {
j = i;
}
idx.push(j);
}
for (let i = n - 1; i >= 0; i--) {
if (list[idx[i]] !== list[i]) {
[list[idx[i]], list[i]] = [list[i], list[idx[i]]];
break;
}
}
let res = 0;
for (let i = n - 1; i >= 0; i--) {
res = res * 10 + list[i];
}
return res;
}(code-box)
impl Solution {
pub fn maximum_swap(mut num: i32) -> i32 {
let mut list = {
let mut res = Vec::new();
while num != 0 {
res.push(num % 10);
num /= 10;
}
res
};
let n = list.len();
let idx = {
let mut i = 0;
(0..n)
.map(|j| {
if list[j] > list[i] {
i = j;
}
i
})
.collect::<Vec<usize>>()
};
for i in (0..n).rev() {
if list[i] != list[idx[i]] {
list.swap(i, idx[i]);
break;
}
}
let mut res = 0;
for i in list.iter().rev() {
res = res * 10 + i;
}
res
}
}(code-box)
Solution 2: Space Optimized Greedy
TypeScriptJavaScript
function maximumSwap(num: number): number {
const ans = [...String(num)];
let [min, max, maybeMax, n] = [-1, -1, -1, ans.length];
for (let i = n - 1; i >= 0; i--) {
if (ans[i] > (ans[maybeMax] ?? -1)) maybeMax = i;
if (i < maybeMax && ans[i] < ans[maybeMax]) {
[min, max] = [i, maybeMax];
}
}
if (~min && ~max && min < max) {
[ans[min], ans[max]] = [ans[max], ans[min]];
}
return +ans.join('');
}(code-box)
function maximumSwap(num) {
const ans = [...String(num)];
let [min, max, maybeMax, n] = [-1, -1, -1, ans.length];
for (let i = n - 1; i >= 0; i--) {
if (ans[i] > (ans[maybeMax] ?? -1)) maybeMax = i;
if (i < maybeMax && ans[i] < ans[maybeMax]) {
[min, max] = [i, maybeMax];
}
}
if (~min && ~max && min < max) {
[ans[min], ans[max]] = [ans[max], ans[min]];
}
return +ans.join('');
}(code-box)
