C++实现找出数字重新排列后小于原数的最大正整数

以下是使用 C++ 实现的解决方案： ```cpp #include <iostream> #include <vector> #include <algorithm> // 函数用于找到符合要求的最大正整数 long long findMaxSmallerNumber(long long n) { std::vector<int> digits; long long temp = n; // 将输入的数字 n 的每一位数字存储到向量 digits 中 while (temp > 0) { digits.push_back(temp % 10); temp /= 10; } // 反转向量，使数字的顺序与原数一致 std::reverse(digits.begin(), digits.end()); // 生成所有可能的排列 std::vector<long long> permutations; do { long long num = 0; // 将排列后的数字组合成一个新的整数 for (int digit : digits) { num = num * 10 + digit; } // 如果新数小于原数 n，则将其添加到排列列表中 if (num < n) { permutations.push_back(num); } } while (std::prev_permutation(digits.begin(), digits.end())); // 如果没有找到符合要求的数字，返回 -1 if (permutations.empty()) { return -1; } // 对排列列表进行排序 std::sort(permutations.begin(), permutations.end()); // 返回最大的符合要求的数字 return permutations.back(); } int main() { long long n; // 读取输入的正整数 n std::cin >> n; // 调用函数找到符合要求的最大正整数 long long result = findMaxSmallerNumber(n); // 输出结果 std::cout << result << std::endl; return 0; } ``` ### 代码解释： 1. **数字拆分**：将输入的数字 `n` 的每一位数字存储到向量 `digits` 中。 2. **生成所有排列**：使用 `std::prev_permutation` 函数生成 `digits` 的所有排列，并将每个排列组合成一个新的整数。 3. **筛选符合要求的数字**：筛选出小于原数 `n` 的数字，并将它们存储在 `permutations` 向量中。 4. **返回最大值**：如果 `permutations` 向量不为空，则对其进行排序并返回最大值；否则返回 -1。 ### 复杂度分析： - **时间复杂度**：$O(k!)$，其中 $k$ 是输入数字 `n` 的位数。因为需要生成所有可能的排列。 - **空间复杂度**：$O(k!)$，主要用于存储所有符合要求的排列。 ######[AI问答 | 660点数解答 | 2026-02-14 20:15:14]