Подсчитайте частоты всех элементов в массиве в O (1) дополнительном пространстве и O (n) времени - PullRequest
Новая
       11

Подсчитайте частоты всех элементов в массиве в O (1) дополнительном пространстве и O (n) времени

0 голосов
/ 26 февраля 2019

Описание проблемы: я нашел эту проблему в своем назначении алгоритмов.Он хочет, чтобы я нашел частоты всех элементов массива в O (n) времени и O (1) пространстве.

Массив Может быть что-нибудь вроде Ar [] = {1,6,3,78, 4,6,1}

Подумав немного, я пришел к такому подходу:

  1. Итерация массива и поиск элемента max. (O (n) time)
  2. Создание нового массива элемента size = max (пробел O (1))
  3. Итерация по исходному массиву и сохранение частот по индексам нового массива (O (n)время).

У меня есть сомнения относительно шага 2. После нахождения максимального элемента (скажем, m) на шаге 1 я создаю новый массив размером m.занимает ли массив вещей O (1) пространство?если нет, пожалуйста, объясните

Ответы [ 3 ]

0 голосов
/ 26 февраля 2019

Без каких-либо предположений относительно вашего ввода, невозможно сделать это за O(n) время и O(1) пробел

  • Наличие O(1) пробела означает, что вы можете установить количествопространство, которое будет выделено заранее.Это означает, что он постоянен (и, следовательно, не зависит от вашего базового массива)
  • Если вы можете ограничить входные данные определенным набором, это станет возможным.Вот некоторые примеры:
    • Когда вы получаете массив char, содержащий кодировку ASCII , тогда вы можете зафиксировать свое пространство в массиве 128 integers.Затем вы перебираете свой ввод и увеличиваете числа в arr[charCode(currentChar)]
    • Массив positive intergers.Вы можете создать массив целых чисел размером Integer.MAX_VALUE, равным 2^32 - 1.Затем примените ту же логику, что и раньше.
0 голосов
/ 27 февраля 2019

Я думаю, что сделать это в O (1) пространстве и O (n) времени будет сложно, если вы не сделаете некоторые предположения, как предлагали некоторые другие ответы.Я не думаю, что выделение массива длины MAXINT - действительно правильный выбор.

Ответ в пространстве O (количество уникальных значений) и O (n) намного проще.Используйте хеш, где ключ - это значение из массива, а хеш-значение - это количество.У вас будет один проход через ваши данные, а затем у вас будет хеш с полными счетами. 

HashMap<Integer,Integer> map.= new HashMap<Integer,Integer>();
for (int value: array) {
   Integer valueI = new Integer(value);
   if (!map.hasKey(valueI)) {
       Integer count = new Integer(1);
       map.put(valueI, count);
   }
   else {
       Integer oldCount = map.get(valueI);
       Integer newCount = new Integer(oldCount.intValue() + 1);
       map.put(valueI, count);
   }
}

Что-то в этом роде.Ключи вашей карты содержат уникальные значения и значения для каждой карты ключей, которые учитываются.

Я не могу придумать что-либо, что вы можете сделать в пространстве O (1), не делая огромных предположений относительно данных, иливыделение действительно огромного массива.В конце концов, вы должны где-то хранить результаты.

0 голосов
/ 26 февраля 2019

Да, вы правильно нашли максимальное число, а затем создание массива хэшей этой длины не является решением проблемы сложности пространства O (1), поскольку сложность пространства O (1) относится к постоянному использованию пространства, но если вы объявляетеРазмер массива основан на ваших входных значениях только тогда, как пространство может быть константой.Постоянное пространство или сложность O (1) означает подход, который не учитывает входные значения, а не зависит от входных данных.Поэтому ваш подход не является правильным решением.Надеюсь, я ясно дал понять.Но если вы хотите решить свою проблему, ее можно найти здесь Geeks for Geeks Это дает хорошее объяснение вашей проблемы.

...