计算不同的数字

Question

有没有什么有效的方法可以在恒定时间或 O(Logn) 内找出给定数字中不同数字的计数？

假设 n = 1234 计数应该是 4（因为有 4 个不同的数字）

如果 n = 1121 计数应该是 2（因为有 2 不同的数字，即 1, 2）

限制条件：0 <= n <= 1000000007

Answer 1

使用地图，键作为数字，值作为计数。现在地图的大小将是你的答案。要么使用集合，因为集合不包含集合的重复元素大小将是您的答案

Answer 2

Pseudo-code:

int DistinctDigits(int n)
{
    int result = 0;
    bool[10] digitFound = {false};

    while (n > 0)
    {
      d = n % 10;
      n = n / 10;

      if (!digitFound[d])
      {
        result++;
        digitFound[d] = true;
      }
    }
    return result;
}

请注意，您必须考虑如何处理前导零（包括当 n == 0 时）。

Answer 3

由于数字（相对）较小，我们可以将它们转换为字符串，通过唯一性过滤器，然后计算元素的数量。例如 Python:

def nuniqdigits(n):
    return len(set(str(n)))

转换成字符串比较费力，我们可以迭代枚举数字如下：

def digits(n):
    if n:
        while n:
            yield n % 10
            n //= 10
    else:
        yield 0

那么我们可以计算出不同数字的数量：

def nuniqdigits(n):
    return len(set(digits(n)))

由于数字的可能值有限，我们可以在这里使用位掩码。例如 Haskell:

import Data.Bits((.|.), popCount, shiftL)
import Data.Word(Word16)

nuniqdigits :: Int -> Int
nuniqdigits n = popCount (foldr (.|.) (0 :: Word16) (map (shiftL 1) (digits n)))
    where digits n | n <= 9 = [n]
                   | otherwise = uncurry (flip (:) . digits) (divMod n 10)

一个数字 n 有 O(log n) 个数字，因为我们在数字的数量上进行迭代，所有操作在每次迭代中都是常数，这在 O(log n).

中运行

计算不同的数字

Counting distinct digits

algorithm

math

number-theory