| comments | difficulty | edit_url | tags | ||
|---|---|---|---|---|---|
true |
中等 |
|
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
示例 2 :
输入: 9973 输出: 9973 解释: 不需要交换。
注意:
- 给定数字的范围是 [0, 108]
我们先将数字转为字符串
接着从左到右遍历
最后将字符串
时间复杂度
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))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));
}
}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);
}
};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
}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;
}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
}
}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('');
}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('');
}