解题思路

题目要求将一个多位数的各位数字重新排列，得到位数不变的最小新数。

比如 231 → 123，23105 → 10235。

注意：第一位不能是 0，否则位数会减少（比如 0123 实际上是 123，只有 3 位）。

方法：

1. 统计每个数字（0~9）出现的次数
2. 先选一个最小的非零数字放在第一位
3. 剩下的数字从小到大依次输出

参考代码

#include <iostream>
#include <string>
using namespace std;

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

    // 统计每个数字出现的次数
    int cnt[10] = {0};
    for (int i = 0; i < s.size(); i++) {
        cnt[s[i] - '0']++;
    }

    // 找到最小的非零数字，放在第一位
    for (int i = 1; i <= 9; i++) {
        if (cnt[i] > 0) {
            cout << i;
            cnt[i]--;
            break;
        }
    }

    // 剩下的数字从小到大依次输出
    for (int i = 0; i <= 9; i++) {
        while (cnt[i] > 0) {
            cout << i;
            cnt[i]--;
        }
    }
    cout << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，N 为数字位数
• 空间复杂度：O(1)