Java C++ 算法题解拓展leetcode670最大交换示例

题目要求

思路：模拟

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

• 这个部分代码似乎有一点小问题【不用似乎就是有】&hellip;&hellip;有就先有着吧&hellip;&hellip;搞了半个小时也没解决【摆烂】

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)

来源：https://juejin.cn/post/7142875009252818975