Подсчитывать числа с одинаковыми цифрами в отсортированном массиве int за O (log n)

Question

Я наткнулся на вопрос на собеседовании, который требовал от кандидата подсчитать все числа в массиве с одинаковыми цифрами.например:

Подсчитать все числа с одинаковыми цифрами с помощью int input = 394 int [] arr = {1, 14, 101, 349, 439, 745, 934}

функциивернет 3, так как 439, 934, 349 имеют одинаковые цифры.Вопрос в том, как решить эту проблему за O (log n)?Я все еще новичок в концепции Большого О, и кроме O (n) и O (n ^ 2) ... у меня возникают проблемы с пониманием того, как архивировать O (log n).

Моя первая мысль быласледует: я бы вычислил сумму цифр всех элементов в массиве.Если сумма равна, они содержат те же цифры, что и входной номер.

      int counter = 0;

      while (num > 0) {
         int digitSum += num % 10;
         num = num / 10;
      }
      for(int i = 0; i < arr.length; i++) {
      int k = arr[i];

      while (k > 0) {
          int sumOfDigits += k % 10;
          k = k/10;
      }
      if(sumOfDigits == digitSum) {
       counter++;
      }
}

Я знаю, что это займет не менее O (n) времени, но у меня возникли проблемы с поиском лучшего решения.

Answer 1

Это решение почти O (n), так как количество цифр на входе очень мало по сравнению с заданным размером массива (n).

Идея состоит в том, чтобы получить минимально возможное число от каждого элемента и сравнитьс соответствующим значением входного номера

public static void main(String []args){

    int input = 394;
    int[] arr = {1, 14, 101, 349, 439, 745, 934};


    int ans = 0;
    int hold = getMin(input);
    for(int i = 0; i < arr.length; i++)
    {
        if(hold == getMin( arr[i] ))
        {
            ans++;
        }
    }
    System.out.println(ans);
}

public static int getMin(int n)
{
    int hold[] = new int[10];
    while( n > 0)
    {
        hold[n % 10]++;
        n /= 10;
    }

    int ans = 0;
    for(int i = 0; i < hold.length; i++)
    {
        while(hold[i] > 0)
        {
            ans = ans * 10 + i;
            hold[i]--;
        }
    }
    return ans;
}

Answer 2

Лучший ответ дали Энди Тернер и Дж. Б. Низет, но, к сожалению, только в качестве комментария:

Чтобы это работало, мы должны принять: размер входного числа ограничен, целые числа в массиведизъюнкт и n - количество элементов в массиве.

1. Вычислить все перестановки входных чисел.Некоторые из перестановок могут быть одинаковыми, если число имеет повторяющиеся цифры, принимайте их только один раз.Это занимает время O (1), а число перестановок также равно O (1).
2. Для каждой перестановки найдите соответствующее число в массиве, используя двоичный поиск, и подсчитайте все попадания.Это занимает O (log n).

В общей сложности вы получаете время выполнения O (log n).

Обратите внимание, что это практично, только если ограничение на число вводадовольно низкий.Если входное число может иметь, скажем, 20 цифр, гораздо лучше использовать метод O (n), если n действительно не огромно.

Answer 3

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

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