Conteggio occorrenze di cifre 'x' nel campo (0, n]

Question

Quindi sto provando a scrivere una funzione python che accetta due argomenti, n e num e conta le occorrenze di 'n' tra 0 e num. ad esempio,

countOccurrences(15,5) dovrebbero essere 2

countOccurrences(100,5) dovrebbe essere 20

ho fatto una semplice soluzione iterativa a questo problema:..

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 

Questo si è verificato in problemi evidenti se ho provato a chiamare countOccurrences(100000000000,5). La mia domanda è: come posso renderlo più efficiente? Voglio essere in grado di gestire il problema "abbastanza" velocemente ed evitare errori di memoria insufficiente. Ecco il mio primo passaggio ad una soluzione ricorsiva cercando di fare questo:

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 

Answer 1

Ho fissato la mia soluzione, e spero che si adatta alle vostre specifiche. Passiamo alla prima funzione di supporto:

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

Questa funzione crea una stringa che elenca tutti i singoli numeri nel numero inserito. Ad esempio,

splitNumber(100) 

sarebbero tornati:

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

Da qui, si chiama la funzione principale e verifica di ogni singolo numero con questa funzione principale:

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 

che dovrebbe dare il desiderato produzione. Fammi sapere se questo funziona per te!

Answer 2

Questo non colpirà alcun problema di memoria, fino a quando lo max_num è abbastanza piccolo da stare in un C long. Fondamentalmente è ancora un algoritmo a forza bruta, anche se significativamente ottimizzato per 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))