Найдите вращение с максимальным расстоянием Хэмминга | Набор 2
Дан целочисленный массив arr[] . Создайте новый массив, который представляет собой вращение данного массива, и найдите максимальное расстояние Хэмминга между обоими массивами.
Hamming distance between two arrays or strings of equal length is the number of positions at which the corresponding character(elements) are different.
Примечание. Для данного входа может быть более одного выхода.
Пример:
Input: arr[] = [1, 4, 1]
Output: 2
Explanation: Maximum hamming distance = 2, this hamming distance with 4 1 1 or 1 1 4
Input: arr[] = [2, 4, 8, 0]
Output: 4
Explanation: Maximum hamming distance = 4, this hamming distance with 4 8 0 2. All the places can be occupied by another digit. Other solutions can be 8 0 2 4, 4 0 2 8 etc.
Подход: Эту проблему можно эффективно решить с помощью Hashmap . Следуйте инструкциям ниже, чтобы решить проблему
- Переберите массив arr[] и сохраните значения массива в HashMap <key, value> . Значение может быть List<> или строкой в зависимости от интереса.
- Добавьте значение в hashmap, hashMap.add(arrvalue, list).
- Проверьте это условие:
- Когда hashMap.contains(arrValue) затем hashmap.get(arrayValue).append(index).
- Проверьте размер хэш-карты, если размер == 1 , то
- максимальное расстояние Хэмминга = 0 . Потому что все ценности одинаковы.
- Запустите для каждого цикла, для каждого ключа, если размер списка = 1 , тогда
- максимальное расстояние Хэмминга = n . Потому что все значения разные.
- Создайте массив размером – 1 из заданного массива для хранения подобных вхождений, которые могут произойти.
- После сохранения всех индексов массива сохраните значения в hashMap .
- Для каждой разницы найдено += 1 . Эта разница говорит о том, сколько оборотов потребуется, чтобы получить одно и то же значение в той же позиции.
- Найдите наименьшее значение в массиве и получите индекс => минимальные одинаковые значения => максимальное расстояние Хэмминга.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)