Много повторяющихся данных и данных есть разные списки для этих данных.
Что бы вы сделали, если бы вам нужно было найти один элемент из двух списков?
List1 = [1,23,35,12,44,86, ……., N]
List2 = [22,35,12,55,78,90,… .., n]
Большинство людей будут использовать для этого Two For Loop следующим образом:
for (int i = 0; i ‹list1.size (); i ++) {
for (int j = 0; int list2.size (); j ++) {
if (list1.get (i) == list2.get (j)) {
printf («Поздравляю! Вы нашли»);
break;
}
}
}
Действительно! подождав это время
Это то, о чем думают все, прежде чем познакомиться с DataStructures. Но это неправильный подход к работе. Я покажу вам, почему и как вы можете это переосмыслить:
- Время и Пространство играют важную роль в Компьютере, поэтому либо вы идете на компромисс со Временем, либо с Пространством, это в основном ваш выбор, и вы должны подумать, что вы собираетесь отбросить для одного. И в этой ситуации время, которое программа берет на 2 цикла, равно O (n2), означает, что вы проходите каждый элемент в цикле, что отнимает у вас много времени.
2. Теперь переходим к этой программе. Пространственная сложность, поэтому вы будете использовать нормальный O (1), потому что вы ничего не сохраняете. Так что это просто сладкий и простой O (1). Каждому программисту нравится O (1), потому что для него не требуется ничего, например 0 и 1.
Теперь мы знаем, что это плохой подход, так какой же подход будет хорошим?
Так что, если проблема связана со Времени, а не с Пространством, давайте пожертвуем нашим Пространством, Простите Пространство, мы не должны делать это с вами.
Мы можем использовать в нашей программе только простую карту!
Теперь давайте посмотрим, как карта поможет нам сделать эту программу с O (n2) до O (n).
Подождите, что O (n)? Да, вы правильно думаете.
Посмотрим на эту программу:
List1 = [1,23,35,12,44,86, ……., N]
List2 = [22,35,12,55,78,90,… .., n]
// Это просто Java-реализация Map, не смотрите на это так, как здесь написано
Карта ‹Длинное, логическое› myMap = new HashMap ‹› ();
// Хорошо, вот что вам нравится
const myMap = новая карта ();
// Сначала мы заполним нашу карту и будем использовать пространство как O (n)
for (int i = 0; i ‹List1.size (); i ++) {
if (! myMap.containsKey (List1.get (i))) {
myMap.put (List1.get (i), истина);
}
}
// А вот и ваша счастливая программа
for (int i = 0; i ‹List2.size (); j ++) {
если (myMap.containsKey (List2.get (j)))
printf («Поздравляю! Вы его нашли»);
}
Теперь поговорим о сложности времени и пространства.
Временная сложность нашего Оптимального решения составляет O (n).
Сложность нашего решения в пространстве - O (n).
Но это лучше, чем иметь O (n2).
Спасибо за чтение!
