LC 0670. Maximum Swap

题目描述

这是 LeetCode 上的 670. 最大交换 - 力扣（LeetCode） ，难度为中等。

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

1. 给定数字的范围是 [0, 10^8]

解答

方法一：模拟

首先取出该数字的每一位整数存储在数组 arr 中，然后遍历数组 arr 的每一位，在其位数的后面寻找最小位上的数字比当前位的数字大的数进行交换，就可以得到比当前数还要大的数，由于要寻找的最小位上的数字是最大的，可能存在多个相同的位数上的最大数相同，此时要选择位数更小的位，所以选择逆序遍历。比如 1992 这个数要选择第二个 9 和 1 交换才能得到更大的数字。

class Solution {
    public int maximumSwap(int num) {
        int[] arr = new int[9];
        int ans = 0, i = 0;
        while (num > 0) {
            arr[i++] = num % 10;
            num /= 10;
        }
        for (int j = i - 1; j >= 0; --j) {
            int idx = j;
            for (int k = 0; k < j; ++k) { // 逆序遍历寻找相同位数最大的最小位
                if (arr[k] > arr[idx]) {
                    idx = k;
                }
            }
            if (idx != j) {
                int tmp = arr[j];
                arr[j] = arr[idx];
                arr[idx] = tmp;
                break;
            }
        }
        for (int k = i - 1; k >= 0; --k) {
            ans += arr[k];
            ans *= 10;
        }
        return ans / 10;
    }
}

• 时间复杂度：\(O((\log_{10}num)^2)\)。

• 空间复杂度：\(O(\log_{10}num)\)。

每题一图