数字重排：求最大最小数 - C++ 实现

数字重排：求最大最小数 - C++ 实现

给定一个数字，如何通过调整数字顺序得到最大数和最小数？例如，数字 9037，调整后最大数为 9730，最小数为 3079。

问题描述

小明有一个数字，现在他想把数字的各个数字调换位置，得到一个最大的数和一个最小的数，你能帮帮他吗？

注： 小明不希望数字的最高位是 0。

输入格式

输入一个数。

输出格式

输出两个数，分别表示调换后的最大数和最小数，以空格隔开。

输入样例

9037

输出样例

9730 3079

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string num;
    cin >> num;

    // 将数字转换为字符数组
    vector<char> digits(num.begin(), num.end());

    // 对字符数组进行排序
    sort(digits.begin(), digits.end());

    // 构造最大数和最小数的字符数组
    vector<char> maxNum(digits);
    vector<char> minNum(digits);

    // 将最大数的字符数组逆序排列
    reverse(maxNum.begin(), maxNum.end());

    // 找到最小数的最高位不为0的数字，与最低位交换
    for (int i = 0; i < minNum.size(); i++) {
        if (minNum[i] != '0') {
            swap(minNum[0], minNum[i]);
            break;
        }
    }

    // 输出最大数和最小数
    for (char digit : maxNum) {
        cout << digit;
    }
    cout << " ";
    for (char digit : minNum) {
        cout << digit;
    }

    return 0;
}

代码解析

1. 将数字转换为字符数组: 使用 vector<char> digits(num.begin(), num.end()); 将输入的数字字符串转换为字符数组。
2. 对字符数组进行排序: 使用 sort(digits.begin(), digits.end()); 对字符数组进行排序，以便后续构造最大数和最小数。
3. 构造最大数和最小数的字符数组: 使用 vector<char> maxNum(digits); 和 vector<char> minNum(digits); 分别创建最大数和最小数的字符数组，并初始化为排序后的数字数组。
4. 将最大数的字符数组逆序排列: 使用 reverse(maxNum.begin(), maxNum.end()); 将最大数的字符数组逆序排列，从而得到最大数。
5. 找到最小数的最高位不为0的数字，与最低位交换: 为了避免最小数的最高位为 0，需要找到最小数的最高位不为 0 的数字，并将其与最低位交换。代码使用 for 循环遍历最小数的字符数组，找到第一个不为 '0' 的数字，并将其与第一个数字交换。
6. 输出最大数和最小数: 使用 for 循环遍历最大数和最小数的字符数组，并依次输出每个数字。

总结

本文介绍了如何通过调整数字顺序得到最大数和最小数，并提供了 C++ 代码实现。该算法利用了排序和字符数组操作，实现简单高效。