剑指Offer面试题32（Java版）：从1到n整数中1出现的次数

女爷i 2022-07-16 04:42 144阅读 0赞

题目：输入一个整数n，求从1到n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11，和12，1一共出现了5次。

**方法一：不考虑时间效率的解法**，靠它拿到Offer有点难：

如果在面试的时候碰到这个问题，应聘者大多能想到最直观的方法，也就是累加1到n中每个整数1出现的次数。我们可疑每次通过对10求余数判断整数的个位数字是不是1.如果这个数字大于10，除以10之后再判断个位数字是不是1.基于这个思路，我们写出下面的代码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.   \* 从1到n整数中1出现的次数 
3.   \*/  
4.  **package** swordForOffer;  
5.    
6.  /\*\* 
7.   \* @author JInShuangQi 
8.   \* 
9.   \* 2015年8月8日 
10.  \*/  
11. **public** **class** E32NumberOf1 \{  
12.     **public** **int** numberOf1BetweenAndN(**int** n)\{  
13.         **int** number = 0;  
14.         **for**(**int** i = 1;i<= n;i++)\{  
15.             number+=numberOf1(i);  
16.         \}  
17.         **return** number;  
18.     \}  
19.     **public** **int** numberOf1(**int** n)\{  
20.         **int** number =0;  
21.         **while**(n!=0)\{  
22.             **if**(n %10 == 1)  
23.                 number++;  
24.             n = n/10;  
25.         \}  
26.         **return** number;  
27.     \}  
28.     **public** **static** **void** main(String\[\] args)\{  
29.         **int** n =12;  
30.         E32NumberOf1 test = **new** E32NumberOf1();  
31.         System.out.println(test.numberOf1BetweenAndN(n));  
32.     \}  
33. \}

从上述思路中，我们对每个数字都要做出发和求余运算以求出该数字中1出现的次数。如果输入数字n，n有O(logn)位，我们需要判断每一位是不是1，那么它的时间复杂度是O(n\*logn)。当输入n非常大的时候，需要大量的计算，运算效率不高。面试官不会满意这种算法。

**方法二：从数字规律着手明显提高时间效率的解法**，能让面试官耳目一新

如果希望不用计算每个数字的1的个数，那就只能寻找1在数字中出现的规律了。为了找到规律，我们不妨用一个稍微大一点的数字比如21345作为例子来分析。我们把从1到21345的所有数字分为两段，一段是从1到1345，另一段是从1346到21345

我们先看从1346到21345中1出现的次数。1出现分为两种情况。首先分析1出现在最高位的情况。从1346到21345的数字中，1出现在10000——19999这10000个数字的万位中，一共出现了10000个。

值得注意的是，并不是对所有的5位数而言在万位出现的次数都是10000个，对于万位是1的数字比如输入12345，1出现在10000——12345的万位，出现的次数不是10000，而是2346次，也就是除去最高位数字之后剩下的数字再加1（即2345+1= 2346）

接下来分析1出现在最高位之外的其他四位数中的情况。例如中1346——21345这20000个数字中后4位中1出现的次数是2000次。由于最高位是2，我们可疑再把1346——21345这20000个数字中后4位出现1出现的次数是2000次。由于最高位是2，我们可以再把1346——21345分为两段，1346——11345和11346——21345.每一段剩下的四位数字中，选择其中一位是1，其余三位可以在0——9这10个数字中任意选择，因此根据排列组合原则总共出现的次数为2\*10（2） = 2000次。

至于从1到1345中1出现的次数，我们可以用递归求得了。这也是我们为什么把1——21345分成1——1345和1346——21345两段的原因。因为把21345的最高位去掉就编程了1345，便于我们采用递归的思路。

public class Solution {
        boolean invalidInput = false;
    
        //时间复杂度为O（logn）
        public int NumberOf1Between1AndN_Solution(int n) {
    
    
    
    
            if(n <= 0){
                invalidInput = true;
                return 0;
            }
    
            StringBuilder s = new StringBuilder(((Integer)n).toString());
    
    
            return NumberOf1(s);
    
        }
    
        int NumberOf1(StringBuilder s){
            if(s == null || s.length() == 0 || s.charAt(0) < '0' || s.charAt(s.length()- 1) > '9'){
                return 0;
            }
    
            int first = s.charAt(0) - '0';
    
            int length = s.length();
    
            if(length == 1 && first == 0){
                return 0;
            }
    
            if(length == 1 && first > 0){
                return 1;
            }
    
            //假设n = 21345
            //numFirstDigit是数字10000 - 19999 的第一个位中的数目
            int numFirstDigit = 0;
            if(first > 1){
                numFirstDigit = PowerBase10(length - 1);
    
            }else if(first == 1){
                numFirstDigit = Integer.parseInt(s.substring(1)) + 1;   
    
            }
            //numOtherDigits是1346 - 21345除了第一位之外的数位中的数目
            int numOtherDigits = first * (length - 1) * PowerBase10(length - 2);
            //numRecursive是1 - 1345中的数目
            int numRecursive = NumberOf1(s.deleteCharAt(0));
    
            return numFirstDigit + numOtherDigits + numRecursive;
        }
    
        int PowerBase10(int n){
            int result = 1;
            for(int i = 0; i < n; i++){
                result *= 10;
    
            }
    
            return result;
        }
    }

[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47372919#