計算數字'x'在範圍（0，n）中的出現次數

因此，我試圖編寫一個接受兩個參數n和num的python函數，並計算0和num之間出現的'n'。例如，計算數字'x'在範圍（0，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

來源

2015-06-29 catagon87

如果這是Python 2.x，請使用'xrange'。遞歸只是意味着你達到了系統遞歸限制。 – jonrsharpe

我相信適當的解決方案可能比這更聰明。我想如果不是O（1），這可以在O（log n）中完成。 – Kevin

我同意其他凱文。我記得在一個編程挑戰網站（Project Euler ???）上看到這個問題，該解決方案是遞歸和對數的。 – Kevin

我有固定我的解決方案，並希望它符合您的要求。讓我們來看看第一個幫助函數：

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

應該給所需輸出。讓我知道這是否適合你！

來源

2015-06-29 16:04:16

內存問題仍然存在於您的解決方案中。在此之上，你不會擺脫額外的Python函數調用和'for'循環。換句話說，你的解決方案與OP的解決方案一樣低效。 –

這不會碰到任何內存問題，直到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))

來源

2015-06-29 16:30:46

計算數字'x'在範圍（0，n）中的出現次數

回答

相關問題