计算数字k在0到n中的出现的次数


https://blog.csdn.net/kkdd2013/article/details/51882774
计算数字k在0到n中的出现的次数,k可能是0~9的一个值
例如n=12,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]中,我们发现1出现了5次 (1, 10, 11, 12)
思路一:我们可以用最简单的办法先尝试一下,遍历1到n中间的每个整数,对每个整数从低位到高位依次检查,如果有k出现则计数器自加。
思路一最大的问题就是效率,当n非常大时,就需要很长的运行时间。想要提高效率,就要避开暴力法,从数字中找出规律。
思路二:来自《编程之美》
假设有一个5位数N=ABCDE,我们现在来考虑百位上出现2的次数,即:从0到ABCDE的数中,有多少个数的百位上是2。分析完它,就可以用同样的方法去计算个位,十位,千位,万位等各个位上出现2的次数。
第一种情况:当百位上的数C小于2时:
1)当百位c为0时,比如说12013,0到12013中哪些数的百位会出现2?我们从小的数起, 200~299, 1200~1299, 2200~2299, … , 11200~11299, 也就是固定低3位为200~299,然后高位依次从0到11,共12个。再往下12200~12299 已经大于12013,因此不再往下。所以,当百位为0时,百位出现2的次数只由更高位决定,等于更高位数字(12)x当前位数(100)=1200个。
2)当百位C为1时,比如说12113。分析同上,并且和上面的情况一模一样。最大也只能到11200~11299,所以百位出现2的次数也是1200个。
上面两步综合起来,可以得到以下结论:
—>当某一位的数字小于2时,那么该位出现2的次数为:更高位数字x当前位数
第二种情况:当百位上的数C等于2时:
当百位C为2时,比如说12213。那么,我们还是有200~299, 1200~1299, 2200~2299, … , 11200~11299这1200个数,他们的百位为2。但同时,还有一部分12200~12213,共14个(低位数字+1)。所以,当百位数字为2时,百位出现2的次数既受高位影响也受低位影响,结论如下:
—>当某一位的数字等于2时,那么该位出现2的次数为:更高位数字x当前位数+低位数字+1
第三种情况:当百位上的数C大于2时:
当百位C大于2时,比如说12313,那么固定低3位为200~299,高位依次可以从0到12,这一次就把12200~12299也包含了,同时也没低位什么事情。因此出现2的次数是: (更高位数字+1)x当前位数。结论如下:
—>当某一位的数字大于2时,那么该位出现2的次数为:(更高位数字+1)x当前位数
通过上述分析,我们可以得到以下规律:
 当某一位的数字小于i时,那么该位出现i的次数为:更高位数字x当前位数
 当某一位的数字等于i时,那么该位出现i的次数为:更高位数字x当前位数+低位数字+1
 当某一位的数字大于i时,那么该位出现i的次数为:(更高位数字+1)x当前位数
    int digitCounts2(int n, int k)
    {
        int result = 0;
        int base = 1;
        while (n/base > 0)
        {
            int cur = (n/base)%10;
            int low = n - (n/base) * base;
            int high = n/(base * 10);

            if (cur == k)
            {
                result += high * base + low + 1;
            } elseif (cur <k)
            {
                result += high * base;
            } else
            {
                result += (high + 1) * base;
            }
            base *= 10;
        }
        return result;
    }

https://blog.csdn.net/zhaoxiangyu1/article/details/47208107
public static int digitCounts(int k, int n) {
    int result = 0;
    int base = 1; //位, 个位/十位/百位
    if (k == 0 && n == 0) {
        return 1;
    }

    while (n / base > 0) {
        int cur = (n / base) % 10;
        int low = n - (n/base) * base;
        int hight = n / (base * 10);

        if (k == 0 && cur > k){
            if (hight != 0) {
                result += hight + 1;
            } else {
                result += hight;
            }
        } else if (cur == k){
            result += hight * base + low + 1;
        } else if (cur < k ){
            result += hight * base;
        } else {
            result += (hight + 1) * base;
        }

        base *= 10;

    }


    return result;
}

http://www.cnblogs.com/cyjb/p/digitOccurrenceInRegion.html
最简单的办法就是依次遍历 1 至 n,再分别求每个数字中 X 出现的次数,代码如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
// 计算数字 X 在 n 中出现的次数。
int countOne(int n, int x) {
    int cnt = 0;
    for (;n > 0;n /= 10) {
        if (n % 10 == x) {
            cnt++;
        }
    }
    return cnt;
}
// 计算数字 X 在 1-n 中出现的次数。
int count(int n, int x) {
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        cnt += countOne(i, x);
    }
    return cnt;
}
int main() {
    printf("%d\n", count(237, 1));
}
这个方法的缺点是时间复杂度太高,countOne 方法的时间复杂度是 O(log10n),count 方法的时间复杂度是 O(nlog10n)
一个更好的办法是利用数学公式直接计算出最终的结果,该方法是依次求出数字 X 在个位、十位、百位等等出现的次数,再相加得到最终结果。这里的 X[1,9],因为 X=0 不符合下列规律,需要单独计算。
首先要知道以下的规律:
  • 从 1 至 10,在它们的个位数中,任意的 X 都出现了 1 次。
  • 从 1 至 100,在它们的十位数中,任意的 X 都出现了 10 次。
  • 从 1 至 1000,在它们的千位数中,任意的 X 都出现了 100 次。
依此类推,从 1 至 10i,在它们的左数第二位(右数第 i 位)中,任意的 X 都出现了 10i1 次。
这个规律很容易验证,这里不再多做说明。
接下来以 n=2593,X=5 为例来解释如何得到数学公式。从 1 至 2593 中,数字 5 总计出现了 813 次,其中有 259 次出现在个位,260 次出现在十位,294 次出现在百位,0 次出现在千位。
现在依次分析这些数据,首先是个位。从 1 至 2590 中,包含了 259 个 10,因此任意的 X 都出现了 259 次。最后剩余的三个数 2591, 2592 和 2593,因为它们最大的个位数字 3 < X,因此不会包含任何 5。
然后是十位。从 1 至 2500 中,包含了 25 个 100,因此任意的 X 都出现了 25×10=250 次。剩下的数字是从 2501 至 2593,它们最大的十位数字 9 > X,因此会包含全部 10 个 5。最后总计 250 + 10 = 260。
接下来是百位。从 1 至 2000 中,包含了 2 个 1000,因此任意的 X 都出现了 2×100=200 次。剩下的数字是从 2001 至 2593,它们最大的百位数字 5 == X,这时情况就略微复杂,它们的百位肯定是包含 5 的,但不会包含全部 100 个。如果把百位是 5 的数字列出来,是从 2500 至 2593,数字的个数与百位和十位数字相关,是 93+1 = 94。最后总计 200 + 94 = 294。
最后是千位。现在已经没有更高位,因此直接看最大的千位数字 2 < X,所以不会包含任何 5。到此为止,已经计算出全部数字 5 的出现次数。
总结一下以上的算法,可以看到,当计算右数第 i 位包含的 X 的个数时:
  1. 取第 i 位左边(高位)的数字,乘以 10i1,得到基础值 a
  2. 取第 i 位数字,计算修正值
    1. 如果大于 X,则结果为 a+10i1
    2. 如果小于 X,则结果为 a
    3. 如果等 X,则取第 i 位右边(低位)数字,设为 b,最后结果为 a+b+1
相应的代码非常简单,效率也非常高,时间复杂度只有 O(log10n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 计算数字 X 在 1-n 中出现的次数。
int count(int n, int x) {
    int cnt = 0, k;
    for (int i = 1;k = n / i;i *= 10) {
        // k / 10 为高位的数字。
        cnt += (k / 10) * i;
        // 当前位的数字。
        int cur = k % 10;
        if (cur > x) {
            cnt += i;
        else if (cur == x) {
            // n - k * i 为低位的数字。
            cnt += n - k * i + 1;
        }
    }
    return cnt;
}
当 X = 0 时,规律与上面给出的规律不同,需要另行考虑。
最主要的区别是,最高位中永远是不会包含 0 的,因此,从个位累加到左起第二位就要结束,需要将上面代码中 for 循环的判断条件改为 k / 10 != 0。
其次是,第 i 位的基础值不是高位数字乘以 10i1,而是乘以 10i11。以 1 至 102 为例,千位中实际包含 3 个 0,但这三个 0 是来自于个位 2 计算得到的修正值,而非来自于基础值。千位的基础值是 0,因为不存在数字 01, 02, 03, ..., 09,即数字前是没有前导 0 的。解决办法就是将上面代码中第 6 行改为 cnt += (k / 10 - 1) * i。
经过综合与化简,得到了以下代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 计算数字 0 在 1-n 中出现的次数。
int countZero(int n) {
    int cnt = 0, k;
    // k / 10 为高位的数字。
    for (int i = 1;(k = n / i) / 10;i *= 10) {
        cnt += (k / 10) * i;
        // k % 10 为当前位的数字。
        if (k % 10 == 0) {
            // n - k * i 为低位的数字。
            cnt += n - k * i + 1 - i;
        }
    }
    return cnt;
}
主要是将一些步骤进行了合并,令代码比较简练。
将上面两段代码进行合并,可以得到以下代码,对 X 从 0 到 9 都有效:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 计算数字 X 在 1-n 中出现的次数。
int count(int n, int x) {
    int cnt = 0, k;
    for (int i = 1;k = n / i;i *= 10) {
        // 高位的数字。
        int high = k / 10;
        if (x == 0) {
            if (high) {
                high--;
            else {
                break;
            }
        }
        cnt += high * i;
        // 当前位的数字。
        int cur = k % 10;
        if (cur > x) {
            cnt += i;
        else if (cur == x) {
            // n - k * i 为低位的数字。
            cnt += n - k * i + 1;
        }
    }
    return cnt;
}

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts