Java C++ 算法题解拓展leetcode670最大交换示例
短信预约 -IT技能 免费直播动态提醒
题目要求
思路：模拟
Java
class Solution {
public int maximumSwap(int num) {
List<Integer> list = new ArrayList<>();
while (num != 0) {
list.add(num % 10);
num /= 10;
}
int n = list.size(), res = 0;
int[] idx = new int[n];
for (int i = 0, j = 0; i < n; i++) {
if (list.get(i) > list.get(j)) // 严格大于
j = i;
idx[i] = j;
}
for (int i = n - 1; i >= 0; i--) { // 高位开始
if (list.get(idx[i]) != list.get(i)) {
int tmp = list.get(idx[i]);
list.set(idx[i], list.get(i));
list.set(i, tmp);
break;
}
}
for (int i = n - 1; i >= 0; i--)
res = res * 10 + list.get(i);
return res;
}
}
- 时间复杂度：O(log num)
- 空间复杂度：O(log num)
C++
class Solution {
public:
int maximumSwap(int num) {
vector<int> list;
while (num != 0) {
list.emplace_back(num % 10);
num /= 10;
}
int n = list.size(), res = 0;
int idx[n];
for (int i = 0, j = 0; i < n; i++) {
if (list[i] > list[j]) // 严格大于
j = i;
idx[i] = j;
}
for (int i = n - 1; i >= 0; i--) { // 高位开始
if (list[idx[i]] != list[i]) {
int tmp = list[idx[i]];
list[idx[i]] =list[i];
list[i] = tmp;
break;
}
}
for (int i = n - 1; i>= 0; i--)
res = res * 10 + list[i];
return res;
}
};
- 时间复杂度：O(log num)
- 空间复杂度：O(log num)
Rust
- 这个部分代码似乎有一点小问题【不用似乎就是有】……有就先有着吧……搞了半个小时也没解决【摆烂】
impl Solution {
pub fn maximum_swap(num: i32) -> i32 {
let mut list = vec![];
let mut res = num;
while (res != 0) {
list.push(res % 10);
res /= 10;
}
let n = list.len();
let mut idx = vec![0; n];
let mut j = 0;
for i in 0..n {
if list[i] > list[j] {
j = i;
}
idx[i] = j;
}
for k in n-1..0 {
if list[idx[k]] != list[k] {
list.swap(idx[k], k);
break;
}
}
for l in n-1..0 {
res = res * 10 + list[l];
}
res
}
}
- 时间复杂度：O(log num)
- 空间复杂度：O(log num)
以上就是Java C++算法题解拓展leetcode670最大交换示例的详细内容，更多关于Java C++算法最大交换的资料请关注编程网其它相关文章！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
