题目解析
* 输入输出:输入一个各位数字互不相同的三位数 NNN;输出经过多少次变换(重排求差)后得到 495495495。
* 数据范围:三位数且各位不同,即 102≤N≤987102 \leq N \leq 987102≤N≤987(不含重复数字)。
* 复杂度要求:时间复杂度 O(C⋅logd)O(C \cdot \log d)O(C⋅logd),其中 CCC 为变换次数(实验表明 C≤6C \leq 6C≤6 即可收敛),d=3d=3d=3 为数字位数;空间复杂度 O(1)O(1)O(1)。
* 算法知识点:模拟、字符串处理、排序、数字重排
思路解析
1. 循环模拟变换:以 N=495N = 495N=495 为终止条件,每次循环执行一次重排求差操作,并用计数器统计次数。
2. 构造最大与最小数:将当前数字转为字符串后,利用 sort 得到升序排列(对应最小数的数字顺序),再 reverse 得到降序排列(对应最大数的数字顺序)。通过 stoi 转回整数后相减,即得新数字。
3. 收敛性保证:数学上,任意无重复数字的三位数经过有限次“重排求差”操作必收敛于 495495495(Kaprekar 常数),因此无需处理无限循环。
完整代码