python统计数字在某个区间内出现的次数

可以使用Python的统计模块collections中的Counter函数来实现。具体代码如下：

from collections import Counter

# 定义一个列表
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# 统计数字在区间[3, 7]内出现的次数
cnt = Counter(x for x in lst if 3 <= x <= 7)

# 输出结果
print(cnt)

输出结果为：

Counter({3: 1, 4: 1, 5: 1, 6: 1, 7: 1})

即数字3、4、5、6、7在区间[3, 7]内分别出现了1次。

相关问题

统计某个给定范围[L,R]内的所有整数中，数字9出席的次数，比如给定范围[88,99]中9出现12次，编写python代码

以下是一个实现上述算法的 Python 代码：

def count_9_between(L, R):
    if L > R:
        return 0
    digits_L = [int(d) for d in str(L)]
    digits_R = [int(d) for d in str(R)]
    n = len(digits_R)
    count = 0
    for i in range(n):
        if i == 0:
            if digits_R[i] < 9:
                count += digits_L[i] * (10 ** (n-i-1))
            elif digits_R[i] == 9:
                count += digits_L[i] * (10 ** (n-i-1)) + 1
            else:
                count += (digits_L[i]+1) * (10 ** (n-i-1))
        else:
            if digits_R[i] < 9:
                count += digits_L[i] * (10 ** (n-i-1))
                count += sum(count_9_between(L, R-10**i)) * (digits_R[i])
            elif digits_R[i] == 9:
                count += digits_L[i] * (10 ** (n-i-1))
                count += sum(count_9_between(L, R-10**i)) * 9
                count += (R // 10**(i-1)) % (10**(i-1)) + 1
            else:
                count += (digits_L[i]+1) * (10 ** (n-i-1))
                count += sum(count_9_between(L, R-10**i)) * 9
                count += (10**(i-1))
    return count

该函数的输入是 L 和 R，输出是 [L,R] 范围内数字9出现的总次数。函数中用到了递归计算子区间内的数字9出现的总次数。注意，该函数的时间复杂度为 O(log R)，因为最多需要递归 log R 层。

请统计某个给定范围[L,R]的所有整数中，数字x出现的次数。 比如给定范围[2,22]，x=2：数字2在该范围内一共出现了6次。

算法1：暴力枚举

对于[L,R]中的每一个数，我们将它转化为字符串，然后遍历字符串中的每一位，如果当前位为x，则计数器加1。最终计数器的值即为数字x在[L,R]中出现的次数。

时间复杂度：O((R-L)logR)

算法2：数位分解

我们可以将[L,R]按照数位分解的方式分成若干个区间，每个区间内的数的某一位都是相同的。比如说，对于区间[1000,2999]，它们的千位上都是1。这样，我们就可以分别计算每个区间内数字x出现的次数，最终把所有区间的计数器相加即可。

具体做法如下：

1. 首先，我们需要求出[L,R]的位数，设为n。比如说，如果L=123，R=7890，那么n=4。

2. 从高到低枚举每一位，设当前枚举的是第i位，范围是[1,n]。我们记[L,R]在第i位之前（高于i位）的数分别为left，右边（低于等于i位）的数分别为right。

3. 对于当前位i，我们分别计算数字x在left、right中出现的次数。设当前位的权值为base（比如说，如果i=2，那么base=10），则在left中，数字x在第i位出现的次数为：

- 如果x=0，那么left中第i位出现0的次数为：(left/base-1+1)×base=left，其中(left/base-1+1)是left中有多少个base的倍数，乘以base就是0出现的次数。
- 如果x>0，那么left中第i位出现x的次数为：(left/base)×base，其中(left/base)是left中有多少个base的倍数，乘以base就是x出现的次数。

在right中，数字x在第i位出现的次数为：

- 如果x=0，那么right中第i位出现0的次数为：(right%base+1)。
- 如果x>0，那么right中第i位出现x的次数为：min(right%base+1, base)。

4. 将所有区间内数字x出现的次数相加，即为答案。

时间复杂度：O(logR)

算法3：数位 DP

我们用f[i][j]表示当前处理到第i位，上一位数字为j时，数字x在[L,R]中出现的次数。转移时可以枚举当前位填哪个数字，然后根据当前位填的数字以及上一位填的数字，计算出当前状态转移到的状态。具体地：

1. 初始化f[0][0]=1，表示处理到第0位时，数字x在[L,R]中出现的次数为0。

2. 从第1位开始枚举每一位，设当前枚举的是第i位，范围是[1,n]。对于每个状态f[i][j]，我们考虑它转移到哪些状态：

- 如果当前位可以填数字x，则状态f[i][j]可以转移到f[i+1][j]，此时数字x在第i位上出现了1次。
- 如果当前位不可以填数字x，则状态f[i][j]可以转移到f[i+1][k]，其中k是当前位可以填的数字，此时数字x在[L,R]中不出现。

3. 最终答案为f[n][0]。

时间复杂度：O(logR)

参考代码：

算法2：

def count_digit(n, x):
    res = 0
    base = 1
    while n > 0:
        left = n // 10
        cur = n % 10
        right = 0
        if x == 0:
            if left > 0:
                left -= 1
                right = base
        res += left * base
        if cur > x:
            res += base
        elif cur == x:
            res += right + 1
        base *= 10
        n //= 10
    return res

L, R, x = map(int, input().split())
ans = count_digit(R, x) - count_digit(L-1, x)
print(ans)

算法3：

L, R, x = map(int, input().split())
n = len(str(R))
f = [[0] * 10 for _ in range(n+1)]
f[0][0] = 1
for i in range(1, n+1):
    for j in range(10):
        for k in range(10):
            if j == x and k != x:
                f[i][j] += f[i-1][k]
            elif j != x:
                f[i][j] += f[i-1][k]
ans = sum(f[n])
if x == 0 and L == 1:
    ans -= sum(f[n-1][:1])
for i in range(1, n):
    ans -= f[i][0]
print(ans)