Java | LeetCode
Задача: 477. Total Hamming Distance
Сложность: medium
Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.
Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.
Пример:
Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
👨💻 Алгоритм:
1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.
2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.
3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.
😎 Решение:
public class Solution {
public int totalHammingDistance(int[] nums) {
int ans = 0;
if (nums.length == 0) {
return ans;
}
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
ans += Integer.bitCount(nums[i] ^ nums[j]);
}
}
return ans;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 431 ·