【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“50.神奇数字在哪里”的解法探究。先来看一下题目内容：
题目详情
等级：中等
知识点：搜索、递归
查看题目：神奇数字在哪里
请计算出1-n(1<=n<=1000000000)中有多少个数字中，只存在'1','2','3'这三个数字，且这三个数字至少都要出现1次。
输入一个数n。
输出1-n中符合要求的数字的个数。
示例1
输入：
232
输出：
4
解题方法：
注意读题，本题要求的数字中“只”含有1，2，3三个数字
方法 1：暴力搜索
对本题，最简单的想法是针对每个数字，转为字符串，然后判断数字中是否只同时包含1，2，3三个字符。鉴于本题输入是int，n最大可以达到2^31-1≈2*10^9，一个这么长的for循环，时间复杂度还是比较高的，不是最优解法。
时间复杂度：O(n)
方法 2：深度优先搜索
寻找这种神奇数字，暴力法可以说是从数字中“尝试”某个数字，是否符合我们的标准，这个过程好比线性搜索。但换个思路想，我们也可以尝试用“构建”的方式，构建出所有符合“神奇数字”标准的数字，并挨个计数，完成这个过程。
这个构建数字和搜索的过程，可以写一个递归做深度搜索实现：从0开始，给一个较短的数字，不断让把的其它位数字移动1位，并把多出来的个位数设为1，2，3，并在搜索的范围超过n时，及时停下搜索。
时间复杂度：O(logn)（或者O(k)，k表示数字的位数）
方法 3：预热+查找
用过方法二后，我们发现，在限定了n是int类型的情况下，其实这种只含有1，2，3的数字的数量并不多。甚至可以在静态初始化方法里，提前计算好所有这样的数字，并按大小排列好。然后对输入的每个n，直接在准备好的数组中二分查找，找到比它小的数字的数量，就可以返回结果了。
看完之后是不是有了答题思路了呢，快来练练手吧：50.神奇数字在哪里
在线编程周赛、月赛火热进行中，更有限时答题活动，社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程内测中，抢先周赛赢好礼！面试考试前，快来刷刷题！
