Как улучшить: учитывая два целых числа, верните количество цифр, которые они разделяют

Ответ 1

Почему бы просто не использовать простую битовку?

public int commonDigits(int x, int y) {
  int dX = 0;
  while (x != 0) {
    dX |= 1 << (x % 10);
    x /= 10;
  }
  int count = 0;
  while (y != 0) {
    int mask = 1 << (y % 10);
    if ((dX & mask) != 0) {
      count ++;
      dX &= ~mask;
    }
    y /= 10;
  }
  return count;
}

Это просто устанавливает соответствующий бит в dX для каждой цифры в x. Во втором цикле для каждой цифры в x код проверяет, имеет ли он запись в dX. Если это так, он подсчитал, а бит reset, чтобы избежать двойного подсчета (обратите внимание, что в коде отсутствует код, рассмотрим 123 и 141). Очевидно, не использует никакого дополнительного хранилища (dX и count могут быть просто байтами, если это имеет значение).

Обратите внимание: вам не нужен HashTable в вашем решении - вы можете просто использовать HasSet или BitSet..

Ваш код переведен на использование BitSet с исправленной проблемой двойного счета:

public int commonDigits(int x, int y) {
  int count = 0;
  BitSet ht = new BitSet();

  while (x != 0) { 
     ht.set(x % 10, true);
     x /= 10;
  }
  while (y != 0) {
     if ((ht.get(y % 10)) {
         count++;
         ht.set(y % 10, false);
     }
     y /= 10;
  }
  return count;
}

Оба фрагмента работают точно так же, последний имеет дополнительные накладные расходы для экземпляра BitSet (и встроенного массива).

В этой статье показано, почему BitSet лучше, чем булевой массив в общем случае: http://chrononsystems.com/blog/hidden-evils-of-javas-byte-array-byte

Изменить:

Если подсчет одной и той же цифры несколько раз действительно желателен (неясно из примеров в вопросе), используйте массив int для хранения счетчиков:

public int commonDigits(int x, int y) {
  int count = 0;
  int[] digits = new int[10];

  while (x != 0) { 
     digits[x % 10]++;
     x /= 10;
  }
  while (y != 0) {
     if (digits[x % 10] > 0) {
         count++;
         digits[x % 10]--;
     }
     y /= 10;
  }
  return count;
}

Ответ 2

Это ваше решение с минимальным хранилищем (массив из 10 байтов вместо хеш-таблицы):

public int commonDigits(int x, int y) {
 int count = 0;
 byte[] digits=new byte[10];

 while (x != 0) { 
     digits[x%10] ++;
     x /= 10;
 }

 while (y != 0) {
     if (digits[y % 10] > 0) {
         count++;
         digits[y % 10] --;
     }
     y /= 10;
 }

return count;
}

Решение оптимально во время работы O(n+m), где n - количество цифр в x, а m - количество цифр в y. Вы не можете сделать меньше, чем перечислять цифры x, а затем цифры y.

Ответ 3

Так как есть только 10 возможных цифр, почему бы просто не сохранить целочисленный массив? Индексировано от 0 до 9, по одному для каждой цифры. Перебирайте каждую цифру и увеличивайте соответствующий элемент массива. Сложность этого пространства зависит от того, что вы определяете как "постоянное" - это всегда займет 10 единиц пространства (будет 10 байтов на C/С++, не уверен, как это работает JVM)

При сохранении информации вы должны прокручивать каждую цифру обоих чисел (они независимы, поэтому вы не можете просто вывести один из другого), поэтому ваша временная сложность останется на уровне O (m + n). Также я думаю, что O (n) вы действительно имеете в виду O (log n), так как это число цифр в любом представлении числа.

Ответ 4

Существует не более 10 цифр, которые могут использоваться совместно. Это означает, что вам не нужна сложная структура данных, такая как Hashtable, массив или битмаска будет достаточно!

Вы просто перебираете первое число, и каждая цифра, которую вы нажимаете, помечена как "истина" (в вашей битовой маске или массиве). Вы можете даже коротко закоротить это и вернуться раньше, если вы нашли каждую цифру один раз (что легко и дешево с помощью битовой маски). Затем переходите второе число. Каждый раз, когда вы нажимаете цифру, также отмеченную как true, увеличивайте счетчик. Если битмаска содержит каждую цифру, короткое замыкание, возвращая длину номера (ее наивысший показатель), в противном случае верните счетчик в конце.

Это не уменьшает сложность O, но уменьшает объем памяти и добавляет некоторые короткие замыкания для больших чисел.

Например, если первым номером является 1234567890, тогда он всегда будет делиться числом цифр со вторым номером, так как второе число имеет десятичные знаки.

Ответ 5

Хэш-таблица является избыточным, просто используйте массив из десяти флагов (независимо от того, упаковываете ли вы их в одно целое с побитовыми операциями или сохраняете независимые переменные).

Сканировать первое целое число и поднять соответствующий флаг для каждой цифры.

Отсканируйте второе целое число и reset соответствующий флаг для каждой цифры.

Возвращает количество истинных сбросов (от 1 до 0).

Обновить: для работы с дубликатами флаги должны быть заменены счетчиками.

Если оба номера имеют M цифр, все они должны быть рассмотрены так, чтобы временная сложность была, конечно, Ω (M).

Случай с пространственной сложностью менее ясен. Все представленные здесь решения - O (N), где N - число возможных цифр (10 в десятичной базе). Но возможно O (1) пространство: возьмите каждую цифру первого числа по очереди, проверьте, является ли это первой такой цифрой в первом номере (чтобы избежать подсчета дубликатов), а затем проверьте, существует ли она во втором номере. Это процесс O (M²) -time, но только O (1) -пространство.

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

Таким образом, можно задаться вопросом, возможно ли решение O (M) -time, O (1) -пространство.

Мое решение - O (M + N) -time, O (N) -пространство. + N в временной сложности требуется только для инициализации всех N флагов. Если вы соглашаетесь не считать инициализацию, вы можете написать алгоритм таким образом, чтобы он очистил все установленные флаги (так что алгоритм можно снова воспроизвести), и это дает O (M) -time, O ( N) -пространственное решение.

Существует простое решение O (M Log M) -time, O (M) -пространство, путем сортировки двух строк цифр и подсчета одинаковых цифр на этапе слияния. Может быть полезным, если M очень мало по сравнению с N.

Ответ 6

В вашем решении не учитываются дубликаты.

# 11, 211 -> 2

Вы правы, чтобы использовать хэш, это быстрее, чем массив. Собираюсь сделать это в python, потому что быстрее набирать...

# Returns an array containing the shared digits
def getShared(num1, num2):
    shared = []
    digits1 = getDigits(num1)
    digits2 = getDigits(num2)
    for digit in digits1:
        if digit in digits2:
            while digits2[digit] > 1 and digits1[digit] > 1:
                digits2[digit] = digits2[digit] - 1
                digits1[digit] = digits1[digit] - 1
                shared += [digit]
            del digits2[digit]
            del digits1[digit]
    return shared

# Given an integer, returns a dictionary with the keys as the digits,
# and the value as the number of times the digit appears
def getDigits(num)
    dict = {}
    while num > 0:
        newDigit = num % 10
        if newDigit not in dict:
            dict[newDigit] = 1
        else:
            dict[newDigit] = dict[newDigit] + 1
    return dict