题目描述

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

示例 1 :

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

示例 2 :

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

注意:

  • 给定数字的范围是 [0, 108]

来源：力扣（LeetCode）

题解

直接遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maximumSwap(int num) {
    char[] chars = String.valueOf(num).toCharArray();
    int maximum = num;
    for (int i = 0; i < chars.length; i++) {
        // 遍历右侧的每个数字
        for (int j = i + 1; j < chars.length; j++) {
            // 交换数字
            swap(chars, i, j);
            // 记录最大值
            maximum = Math.max(maximum, Integer.parseInt(new String(chars)));
            // 恢复原装
            swap(chars, i, j);
        }
    }
    return maximum;
}

private void swap(char[] charArr, int i, int j) {
    char temp = charArr[i];
    charArr[i] = charArr[j];
    charArr[j] = temp;
}
  • 时间复杂度： O(log^3num)*，其中整数 num 为给定的数字。num 转换为十进制数，有 *O(lognum) 个数字，一共有 O(log^2num) 种不同的交换方法，每种方法需要重新构造一个新的整数，需要的时间为 *O(lognum)*，因此总的时间复杂度为 *O(log^3num)*。
  • 空间复杂度： O(lognum)*，其中整数 num 为给定的数字。num 转换为十进制数，有 *O(lognum) 个数字，需要保存 num 所有的数字。

submissions-2022091301

贪心

右边越大的数字与左边较小的数字进行交换，这样产生的整数才能保证越大。因此我们可以利用贪心法则，尝试将数字中右边较大的数字与左边较小的数字进行交换，这样即可保证得到的整数值最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maximumSwap(int num) {
    char[] chars = String.valueOf(num).toCharArray();
    // 记录最大数字的下标
    int max = chars.length - 1;
    // 记录交换数字的下标
    int i = -1, j = -1;
    for (int k = chars.length - 1; k >= 0; k--) {
        if (chars[k] > chars[max]) {
            max = k;
        } else if (chars[k] < chars[max]) {
            i = k;
            j = max;
        }
    }
    // 如果 i 不是 -1 证明需要交换数字, 即 num 本身构成数字不是从大到小排列的
    if (i >= 0) {
        swap(chars, i, j);
        return Integer.parseInt(new String(chars));
    }
    return num;
}
  • 时间复杂度： O(lognum)*，其中整数 num 为给定的数字。num 转换为十进制数，有 *O(lognum) 个数字，需要遍历一次所有的数字即可。
  • 空间复杂度： O(lognum)*，其中整数 num 为给定的数字。num 转换为十进制数，有 *O(lognum) 个数字，需要保存 num 所有的数字。

submissions-2022091302

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 选择排序
public int maximumSwap(int num) {
    char[] chars = String.valueOf(num).toCharArray();
    // 从最高位开始循环, 如果最高位的数字不是最大的, 那么从下标 i + 1 到 nums.length 中的最大值与最高位数字交换
    for (int i = 0; i < chars.length; i++) {
        // 存储右侧最大值的下标
        int index = i;
        // 为何要从右向左循环? 因为如果要交换, 那么下标 i 的元素一定小于下标 index 的元素. 将小的数字交换过来, 当然是越靠右越好（如果存在相同元素）
        for (int j = chars.length - 1; j > i; j--) {
            if (chars[j] > chars[index]) index = j;
        }
        // 如果最大值的下标变化, 那么证明最大值存在
        if (index != i) {
            swap(chars, i, index);
            return Integer.parseInt(new String(chars));
        }
    }
    // 如果从循环中结束, 说明这个数字每个位置的数字按照从大到小排列, 无需进行交换
    return num;
}

private void swap(char[] charArr, int i, int j) {
    char temp = charArr[i];
    charArr[i] = charArr[j];
    charArr[j] = temp;
}
  • 时间复杂度： O(n^2)
  • 空间复杂度： O(n)

submissions-2022091303

参考资料

__END__