python 从0到n的数字中数字出现的次数

btqmn9zl 于 2022-10-30 发布在 Python

关注(0)|答案(6)|浏览(255)

给定一个数n，计算数字0、2和4（包括n）的出现次数。
范例1：

n = 10
output: 4

示例2：

n = 22
output: 11

我的代码：

n = 22

def count_digit(n):
    count = 0
    for i in range(n+1):
        if '2' in str(i):
            count += 1
        if '0' in str(i):
            count += 1
        if '4' in str(i):
            count += 1
    return count

count_digit(n)

程式码输出：11
所需输出：11个
限制条件：1 <= N <= 10^5
注意：对于较大得数字，该解决方案不应导致outOfMemoryException或Time Limit Exceeded.

python

来源：https://stackoverflow.com/questions/73821319/number-of-occurrences-of-digit-in-numbers-from-0-to-n

6条答案

按热度按时间

9lowa7mx1#

您可以按如下方式递增计数：

def count_digit(n):
    count = 0
    for i in range(n + 1):
        if '2' in str(i):
            count += str(i).count('2')
        if '0' in str(i):
            count += str(i).count('0')
        if '4' in str(i):
            count += str(i).count('4')
    return count

这样，像22、44等这样的边缘情况就被覆盖了！

赞(0）回复(0）举报 2022-10-30

izkcnapc2#

有些数字中重复了所需的数字，如20或22，因此必须加上2，而不是加上1

>>> 
>>> string = ','.join(map(str,range(23)))
>>> 
>>> string
'0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22'
>>> 
>>> string.count('0') + string.count('2') + string.count('4')
11
>>> 

n = 22

def count_digit(n):
    count = 0
    for i in map(str,range(n+1)):

        count+=i.count('0')
        count+=i.count('2')
        count+=i.count('3')
    return count
print(count_digit(n))

该解决方案是快速：它可以开发得更快：

def count_digit(n):
    i=0
    count=0
    s='024'
    while i<n-1:

        j = 0
        for v in str(i):
            if v in s:
                j+=1

        count+=3*j + (7*(j-1))
        i+=10

    for i in range(i,n+1,1):
        for v in str(i):
            if v in s:
                count+=1

    return count

赞(0）回复(0）举报 2022-10-30

krugob8w3#

TL;DR：如果操作正确，对于接近10**5的 n，计算计数的速度可以快1000倍，而且由于更好的算法使用的时间与 n 中的位数成正比，因此即使 n 的值对于64位整数来说太大，它也可以轻松处理。
像这样的谜题通常都是这样（“在从x到y的数字中，有多少个......？”），关键是要找到一种方法来计算聚合计数，理想情况下是在O（1），对于一个大的值域。对于数字的字符串表示的组合学，一个方便的值域通常是类似于所有数字的集合，这些数字的字符串表示是给定的大小，也就是说，[prefix*10⁴, prefix*10⁴+9999]形式的范围，其中下限中的0与上限中的9的个数以及乘数中的10的指数相同。（实际上，使用半开区间更方便，其中下限包含在内，上限不包含在内，因此上面的例子是[prefix*10⁴, (prefix+1)*10⁴)。）
还要注意，如果问题是计算[x，y）的计数，而您只知道如何计算[0，y），则只需执行两次计算，因为

count [x, y) == count [0, y) - count [0, x)

这个恒等式是半开区间所允许的简化之一。
这对这个问题来说很有效，因为在给定前缀的k位后缀集合中，一个数字 d 出现的次数是很清楚的（在10k 个后缀中，每个数字与其他数字的出现频率相同;在这10k 中总共有 k×10k 个数字，由于所有数字都有相同的计数，这个计数必须是 k×10k−1。）然后你只需要把前缀的数字计数相加，但是前缀正好出现了10k 次，并且每一次都贡献了相同的计数。
因此，你可以把72483这样的数字分解成以下几个区间，这些区间大致相当于72483的数字总和，再加上一些包含较少数字的区间。

[第0页，9页]
[第10、99段]
【100，999】
【1000，9999】
[万，19999]
【20000年，29999年】
【30000，39999】
【40000，49999】
【50000，59999】
【60000，69999】
【70000，70999】
[71000，71999]
【72000，72099】
【72100，72199】
【72200，72299】
【72300，72399】
【72400，72409】
【七二四一零，七二四一九】
【七二四二零，七二四二九】
【七二四三，七二四三九】
【72440，72449】
【七二四五零，七二四五九】
【72460，72469】
【七二四七零，七二四七九】
【七二四八，七二四八】
【七二四八一，七二四八一】
【七二四八二，七二四八二】
【七二四八三，七二四八三】

然而，在下面的代码中，我使用了一个稍微不同的算法，结果发现它更短一些。它考虑了一个矩形，其中从0到n的所有数字都被写出，包括前导零，然后计算每一列的计数。一个连续整数矩形中的一列数字遵循一个简单的循环模式;从列中完全重复的部分开始，可以很容易地计算出频率。在完全重复之后，剩下的数字按顺序排列，除了最后一个数字之外，每个数字都出现相同的次数。在一张纸上画一个小例子可能是最容易理解的，但是下面的代码也应该相当清楚（我希望如此）。
这样做的一个问题是，它计算的前导零实际上并不存在，因此需要通过减去前导零来纠正。幸运的是，这个计数非常容易计算。如果你考虑一个以五位数结尾的范围（它本身不能以零开头，因为如果它以零开头，它就不是真正的五位数），您可以看到范围包括：

10000个数字以零开头
还有1000个第二个前导零的数字
还有100个第三个前导零的数字
再加10个第四个前导零的数字没有一个数字有五个前导零，因为我们把0写成这样，而不是空字符串。

这两个数字之和为11110，很容易看出它是如何推广的，这个值可以不用循环计算，即（10 -1）/ 9 − 1，这个修正在下面的函数末尾完成：

def countd(m, s=(0,2,4)):
    if m < 0: return 0
    m += 1
    rv = 0

    rest = 0
    pos = 1
    while True:
        digit = m % 10
        m //= 10
        rv += m * pos * len(s)
        for d in s:
            if digit > d:
                rv += pos
            elif digit == d:
                rv += rest
        if m == 0:
            break
        rest += digit * pos
        pos *= 10
    if 0 in s:
        rv -= (10 * pos - 1) // 9 - 1
    return rv

几乎可以肯定的是，这一准则可以得到加强;我只是想把算法写下来，但是，实际上，它的执行时间是以微秒为单位，而不是毫秒，即使 n 的值大得多。
下面是Kelly基准测试的更新;我删除了其他解决方案，因为它们在 n 的最后一个值上花费的时间太长：
在线试用！

赞(0）回复(0）举报 2022-10-30

zte4gxcn4#

另一股蛮力，似乎更快：

def count_digit(n):
    s = str(list(range(n+1)))
    return sum(map(s.count, '024'))

n = 10**5基准测试：

result   time   solution

115474  244 ms  original
138895   51 ms  Kelly
138895  225 ms  islam_abdelmoumen
138895  356 ms  CodingDaveS

代码（在线试用！）：

from timeit import default_timer as time

def original(n):
    count = 0
    for i in range(n+1):
        if '2' in str(i):
            count += 1
        if '0' in str(i):
            count += 1
        if '4' in str(i):
            count += 1
    return count

def Kelly(n):
    s = str(list(range(n+1)))
    return sum(map(s.count, '024'))

def islam_abdelmoumen(n):
    count = 0
    for i in map(str,range(n+1)):
        count+=i.count('0')
        count+=i.count('2')
        count+=i.count('3')
    return count

def CodingDaveS(n):
    count = 0
    for i in range(n + 1):
        if '2' in str(i):
            count += str(i).count('2')
        if '0' in str(i):
            count += str(i).count('0')
        if '4' in str(i):
            count += str(i).count('4')
    return count

funcs = original, Kelly, islam_abdelmoumen, CodingDaveS

print('result   time   solution')
print()
for _ in range(3):
    for f in funcs:
        t = time()
        print(f(10**5), ' %3d ms ' % ((time()-t)*1e3), f.__name__)
    print()

赞(0）回复(0）举报 2022-10-30

wj8zmpe15#

最后我得到了一个与rici的答案相似的答案，只是在数字的表达上可能略有不同。（正如rici所描述的，“每列计数”）我们可以用两部分来表示，首先是p * floor(n / (10 * p))，其中p是10的位置幂。（最右边），每十个数字有一个1。但是，计算0的数量需要对当前和下一个位置的人口进行额外的检查。
对于第一部分，我们仍然需要将除法的余数的计数相加。例如，对于n = 6，floor(6 / 10) = 0，但我们有一个2的计数和一个4的计数。如果n中那个位置的数字大于我们正在计数的数字，我们就加上p;或者，如果数字相同，则将数字右侧的值加1（例如，对于n = 45，我们希望计算4出现在位置1的6个示例：第40条、第41条、第42条、第43条、第44条、第45条）。
JavaScript代码，与rici的代码进行比较，立即获得从1到600,000的 * 所有 * 数字。（如果我没有弄错的话，rici的代码错误地为n = 0返回0，而答案应该是1计数。

function countd(m, s = [0,2,4]) {
  if (m <= 0)
    return 0
  m += 1
  rv = 0
  rest = 0
  pos = 1
  while (true) {
    digit = m % 10
    m = Math.floor(m / 10)
    rv += m * pos * s.length
    for (d of s) {
      if (digit > d)
        rv += pos
      else if (digit == d)
        rv += rest
    }
    if (m == 0) {
      break
    }
    rest += digit * pos
    pos *= 10
  }
  if (s.includes(0)) {
    rv -= Math.floor((10 * pos - 1) / 9) - 1
  }
  return rv
}

function f(n, ds = [0, 2, 4]) {
  // Value on the right of position
  let curr = 0;
  let m = n;
  // 10 to the power of position
  let p = 1;
  let result = 1;

  while (m) {
    const digit = m % 10;
    m = Math.floor(m / 10);
    for (const d of ds) {
      if (d != 0 || n >= 11 * p) {
        result += p * Math.floor((n - (d ? 0 : 10 * p)) / (10 * p));
      }
      if (digit > d && (d != 0 || m > 0)) {
        result += p;
      } else if (digit == d) {
        result += curr + 1;
      }
    }
    curr += p * digit;
    p *= 10;
  }

  return result;
}

for (let n = 1; n <= 600000; n += 1) {
  const _f = f(n);
  const _countd = countd(n);
  if (_f != _countd) {
    console.log(`n: ${ n }`);
    console.log(_f, _countd);
    break;
  }
}

console.log("Done.");

赞(0）回复(0）举报 2022-10-30

hfyxw5xn6#

使用in而不是多分支条件。

def count_digit(n):
    s = '024'
    out = 0
    for cs in map(str, range(n+1)):
        for c in cs:
            if c in s:
                o += 1
    return out

或更紧凑地

def count_digit(n):
    s = '024'
    return sum(1 for cs in map(str, range(n+1)) for c in cs if c in s)

赞(0）回复(0）举报 2022-10-30

我来回答

python 从0到n的数字中数字出现的次数

6条答案

相关问题

热门标签

最新问答