Уровень: easy
В алгоритмических задачах, на мой взгляд, важно не только решить, но и объяснить (в первую очередь самому себе🤫), почему ты выбрал тот или иной подход.
Итак, легкая задачка: дан массив чисел nums, нужно вернуть кол-во пар равных элементов (nums[i] == nums[j]), где i < j.
Например, массив [5, 9, 2, 5, 2, 2]:
- Индексы равных пар: (0, 3), (2, 4), (2, 5), (4, 5)
- Ответ: 4
Ограничения:
1. Длина массива от 1 до 100
2. Числа в массиве от 1 до 100
Ссылочка на задачу, как всегда.
Существует два решения, которые приходят на ум (конечно, можно сделать больше решений, но остановимся на 2-ух).
Первый вариант: Хэш-таблица
Код:
public int numIdenticalPairs(int[] nums) {
int goodPairs = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int num: nums) {
if (map.containsKey(num)) {
goodPairs += map.get(num);
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
return goodPairs;
}Алгоритм:
1. Заводим хэш-таблицу map и переменную, где будет храниться ответ goodPairs
2. Проходимся по каждому элементу массива и проверяем, есть ли уже такой ключ (с текущим значением массива) в хэш-таблице:
- ключа нет - добавляем, записывая в ключ - значение массива, а в значение единицу (текущее кол-во повторений)
- ключ есть - получаем по ключу значение из хэш-таблицы (кол-во повторений), увеличиваем счетчик goodPairs, перезаписываем в хэш-таблицу значение массива с увеличенным на "1" кол-вом повторений.
3. Возвращаем результат goodPairs
Временная сложность: O(n) -т.к. пройдемся по каждому элементу массива один раз.
Пространственная сложность: O(n) - худший случай, если все элементы массива уникальны и придется выделить память под каждый элемент в хэш-таблице. O(1) - лучший случай, если все элементы равны.
Второй вариант: массив
Однако, в текущих ограничениях - значения от 0 до 100, мы можем выделить фиксированное значение памяти и улучшить пространственную сложность до O(1).
Код:
public int numIdenticalPairs(int[] nums) {
int goodPairs = 0,
elements[] = new int[101];
for (int num: nums) {
goodPairs += elements[num]++;
}
return goodPairs;
}1. Выделяем память под результат - goodPairs.
2. Создаем массив elements размером 101 для подсчета количества встреч каждого значения в массиве. Этот массив покрывает диапазон значений от 0 до 100 (подходит под наши ограничения)
3. Идем по каждому элементу массива nums, увеличивая счетчик goodPairs на текущее значение счетчика elements[num].
Это работает, потому что если элемент num уже встречался ранее, значит, он может образовать "хорошие пары" с каждым из предыдущих вхождений этого элемента.
4. Увеличиваем счётчик elements[num] на единицу, чтобы учесть текущее вхождение элемента.
5. Возвращаем результат
Важно: такой подход будет эффективен только на небольших отрезках чисел (как в этой задаче). Если ограничение станет, скажем в пределах значений int или long - массив сожрет много памяти, а это нам не нужно. Тогда будет эффективнее использовать хэш-таблицу.