Подсчет разных цифр

Question

Есть ли эффективный способ узнать количество различных цифр от заданного числа в постоянное время или O (Logn)?

Предположим, n = 1234 количество должно быть 4 (поскольку существует 4 различных цифр)

если n = 1121 количество должно быть 2 (поскольку есть 2 различных цифр, т. Е. 1, 2)

Ограничение: 0 <= n <= 1000000007

Answer 1

Псевдокод:

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 2

использовать карту с ключом в качестве цифры и значением в качестве ее числа. Теперь размер карты будет вашим ответом. или же используйте набор, так как набор не содержит дубликат элемента, размер которого будет вашим ответом

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) .