在区间[0，n]中统计数字'x'出现的次数

Question

我正在尝试编写一个Python函数，它接受两个参数n和num，并计算0到num之间'n'的出现次数。例如， countOccurrences(15,5) 应该是 2。 countOccurrences(100,5) 应该是 20。

我为这个问题设计了一个简单的迭代解决方案：

def countOccurrences(num,n):
  count=0
  for x in range(0,num+1):
    count += countHelper(str(x),n)
  return count

def countHelper(number,n):
  count=0
  for digit in number:
    if digit==n:
      count += 1
  return count

如果我尝试调用countOccurrences(100000000000,5)，这会遇到明显的问题。

我的问题是如何使这个过程更加高效？我希望能够"相对"快速地处理问题，并避免内存错误。下面是我第一次尝试递归解决此问题：

def countOccurence(num, n):
  if num[0]==n:
    return 1
  else:
    if len(num) > 1:
      return countOccurence(num[1:],n) + countOccurence(str((int(num)-1)),n)
    else:
      return 0

- catagon87

---

如果这是Python 2.x，请使用xrange。递归只会导致您达到系统递归限制。 - jonrsharpe

我相信正确的解决方案可能比这个聪明得多。如果不是O(1)，我想这可以在O(log n)内完成。 - Kevin

我同意另一个Kevin的观点。我记得在一个编程挑战网站（Project Euler？？？）上看到过这个问题，并且解决方案是递归和对数的。 - Kevin

可能是重复的问题：如何计算整数范围内每个数字的出现次数？ - Pham Trung

你可以使用非常类似的解决方案来获得O(log n)：https://dev59.com/DGEh5IYBdhLWcg3wbjPd#22394258 - Niklas B.

这是一个反向问题吗？https://dev59.com/k4Pba4cB1Zd3GeqPpT38? - גלעד ברקן

Answer 1

除非max_num小到能够适应C语言的long类型，否则这不会遇到任何内存问题。基本上它仍然是一个暴力算法，但已经针对Python进行了显着优化。

def count_digit(max_num, digit):
    str_digit = str(digit)
    return sum(str(num).count(str_digit) for num in xrange(max_num+1))

- Eli Korvigo

Answer 2

我已经修复了我的解决方案，希望它符合您的规格要求。让我们来看看第一个辅助函数：

def splitNumber(num):
    temp = str(number)
    nums = list(temp)
    return nums

这个函数创建一个字符串列表，其中包含数字输入中的所有单个数字。例如，

splitNumber(100)

将返回：

['1', '0', '0']

从这里开始，您可以调用主函数并使用该主函数测试每个单独的数字：

def countOccurences(num, n):
    count = 0
    for x in range(0, (num + 1)):
        temp = splitNumber(x)
        for x in range(len(temp)):
            if (temp[x] == str(n)):
                count = count + 1
    return count

这应该会给出所需的输出。如果这对你有用，请告诉我！

- Usman Tahir

---

你的解决方案仍存在内存问题。此外，你没有摆脱额外的Python函数调用和for循环。换句话说，你的解决方案与OP的一样低效。 - Eli Korvigo

这只是上面解决方案的较慢版本，而上面的解决方案本身就很慢。 - arjunsiva

Answer 3

请参见：https://math.stackexchange.com/a/1229292/974150 在Python中：

def counts_of_i_bf(n, i):
    """Counts the number of occurences in a range [0 .. n] of
        the digit i [0...9]

    Args:
        n ([int]): upper value of range [0 ... n]
        i ([type]): digit looking for [0.. 9]

    Returns:
        [int]: occurences of i in the range [0...n]
    """
    return sum(str(d).count(str(i)) for d in range(n + 1))

def counts_of_i_dp(n, i):
    """Counts the number of occurences in a range [1 .. n] of
        the digit i [1...9] by implementing the recurrence
        relation:
                        | ak.10^(k-1) + fi(b)           if a < i
        fi(a.10^k +b) = | ak.10^(k-1) + 1 + fi(b) + b   if a == i
                        | (ak + 10).10^(k-1) + fi(b)    if a > i

    see: https://math.stackexchange.com/a/1229292/974150
    Args:
        n ([int]): upper value of range [1 ... n]
        i ([type]): digit looking for [1.. 9]

    Returns:
        [int]: occurences of i in the range [0...n]
    """
    som = 0
    while n > 0:
        k = int(log10(n))
        a = n // 10**k
        b = n - a * 10**k
        if a < i:
            som += a*k*10**(k-1)
        elif a == i:
            som += a*k*10**(k-1) + 1 + b
        else:
            som += (a*k + 10)*10**(k-1)
        n = b
        
    return int(som)

def counts_of_0(n):
    """Counts the number of occurences in a range [1 .. n] of
        the digit0 by implementing:
        Tn = (k + 1)*(b + 1 + (a - 1)10^k) + ∑ 9*s*10(s - 1) for s=1.. k\
        f0(n) = Tn -∑ 9s.10^(s-1) for s=1..9
  
        see: https://math.stackexchange.com/a/1229292/974150
    Args:
        n ([int]): upper value of range [1 ... n]

    Returns:
        [int]: occurences of 0 in the range [1...n]
    """
    k = int(log10(n))
    a = n // 10**k
    b = n - a * 10**k
    Tn = (k + 1)*(b + 1 + (a - 1)*10**k) + sum(9*s*10**(s - 1) for s in range(1, k + 1))
    return Tn - sum(counts_of_i_dp(n, i) for i in range(1, 10)) + 1 # was one of


def counts_of_i(n, i):
    """Counts the number of occurences in a range [0 .. n] of
        the digit i [0...9]
        

    Args:
        n ([int]): upper value of range [0 ... n]
        i ([type]): digit looking for [0.. 9]

    Returns:
        [int]: occurences of i in the range [0...n]
    """
    if n == 0: return 1 if i == 0 else 0
    if i == 0: return counts_of_0(n)
    return counts_of_i_dp(n, i)

assert all(counts_of_i_bf(i, d) == counts_of_i(i, d) for i in range(1_001) for d in range(10))

- user7850571

---

这看起来非常有前途，但一些算法的解释会很有用。此外，counts_of_i_dp(10,0)返回一个值为11，这不可能是正确的。 - r3mainer