海明距离计算 php,[LeetCode 477]PHP 计算汉明距离总和

向右看齐 2022-11-18 05:49 115阅读 0赞

PHP 计算汉明距离总和

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。

示例:输入: 4, 14, 2

输出: 6

解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。(这样表示是为了体现后四位之间关系)

所以答案为：

HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

注意:数组中元素的范围为从 0到 10^9。

数组的长度不超过 10^4。

解题思路 1

穷举两两组合的数量，然后累加汉明距离，这个是最简单直白的方案。

结果是大量数据的时候会超时，阶乘的数量太多。

代码class Solution \{

/\*\*

\* @param Integer\[\] $nums

\* @return Integer

\*/

function totalHammingDistance($nums) \{

$count = count($nums);

$sum = 0;

for ($i = 0; $i < $count - 1; $i++) \{

for ($j = $i+1; $j < $count; $j++)

\{

$sum += $this->hm($nums\[$i\], $nums\[$j\]);

\}

\}

return $sum;

\}

// 汉明距离方法

function hm($x, $y)

\{

return substr\_count(decbin($x ^ $y), '1');

\}

\}

解题思路 2 - 竖着计算我们经常会这样分析问题：最简单的情况 -> 一般的、复杂的情况。之前我们是：遍历所有可能的两两组合。

现在我们换一个角度看：如果int只有1位-> int有32位。

首先，如果 int 只有 1 位，即数组 nums 中的元素只有两种情况，0 或者 1，此时求汉明距离总和的步骤如下：首先将数组分成两组，全 0 位一组，全 1 位一组

将两组数两两组合，记一个为a，一个为b

如果 a、b 均来自 0 那一组，或者均来自 1 那一组，此时不会有汉明距离产生。但是如果 a、b 一个来自 0 那一组，另外一个来自1那一组，这时将会产生汉明距离

假设 nums 数组元素个数为 n，其中 0 元素个数为 k，则 1 元素的个数为 n-k，则上一步能够产生汉明距离的总和就是k\*(n-k)

k\*(n-k) 就是 int 只有 1 位的情况下的汉明距离总和

如果将 int 的位数从 1 位扩展到 32 位，那么就是将遍历每一位，然后求出在这一位上的汉明距离和，累加到一起，这样可以将算法复杂度从 $O(N^2)$ 降低到 $O(32\\\\times N)$，即为 $O(N)$。

可以看下面这个例子：十进制 二进制

4: 0 1 0 0

14: 1 1 1 0

2: 0 0 1 0

1: 0 0 0 1

先看最后一列，有三个 0 和一个 1，那么它们之间相互的汉明距离就是 3，即 1 和其他三个 0 分别的距离累加，然后在看第三列，累加汉明距离为 4，因为每个 1 都会跟两个 0 产生两个汉明距离，同理第二列也是 4，第一列是 3。各列相互之间两两组合的汉明距离总和就是各列 0 的个数与 1 的个数之和，把各列汉明距离总和再累加就是题目所求的数组 nums 元素两两之间的汉明距离总和。

代码class Solution \{

/\*\*

\* @param Integer\[\] $nums

\* @return Integer

\*/

function totalHammingDistance($nums) \{

$count = count($nums);

$sum = 0;

for($i = 0; $i < 32; $i++)

\{

$tmpCount = 0;

for($j = 0; $j < $count; $j++)

\{

$tmpCount += ($nums\[$j\] >> $i) & 1;

\}

$sum += $tmpCount \* ($count - $tmpCount);

\}

return $sum;

\}

\}

参考链接

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关 C/C++计算汉明距离

什么是汉明距离汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示的是两个数字对应二进制不同的位置的数量. 汉明距离的实现

女爷i/ 2022年12月10日 07:25/ 0 赞/ 117 阅读

相关海明距离计算 php,[LeetCode 477]PHP 计算汉明距离总和

PHP 计算汉明距离总和两个整数的汉明距离指的是这两个数字的二进制数对应位不同的数量。计算一个数组中，任意两个数之间汉明距离的总和。示例:输入: 4, 14,

向右看齐/ 2022年11月18日 05:49/ 0 赞/ 116 阅读

相关 LeetCode477 : 汉明距离总和

考察点：位运算（异或操作对比位数差异、bitCount函数统计1个个数、位运算时的数学思维） public class LeetCode477totalHammin

╰半夏微凉°/ 2022年10月16日 09:40/ 0 赞/ 140 阅读

相关 477. 汉明距离总和

2021-05-28 LeetCode每日一题链接：[https://leetcode-cn.com/problems/total-hamming-distance/]

矫情吗；*/ 2022年10月16日 08:55/ 0 赞/ 115 阅读

相关 477. 汉明距离总和

两个整数的汉明距离指的是这两个数字的二进制数对应位不同的数量。计算一个数组中，任意两个数之间汉明距离的总和。示例: 输入: 4, 14, 2 输出: 6 解释

￡神魔★判官ぃ/ 2022年10月16日 07:53/ 0 赞/ 113 阅读

相关 461. 汉明距离

2021-05-27 LeetCode每日一题链接：[https://leetcode-cn.com/problems/hamming-distance/][https

男娘i/ 2022年10月16日 07:18/ 0 赞/ 125 阅读

相关算法 - 计算汉明距离

> [算法 - 计算汉明距离][-] 1. 题目给出两个整数 x 和 y，计算它们之间的汉明距离。 > `汉明距离`是使用在数据传输差错控制编码里面的，汉明距离是一

ゞ浴缸里的玫瑰/ 2022年10月16日 06:17/ 0 赞/ 121 阅读

相关 461. 汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。注意： 0 ≤ x, y < 231. 示例

你的名字/ 2022年10月16日 06:15/ 0 赞/ 120 阅读

相关 leetcode 477. Total Hamming Distance | 477. 汉明距离总和

题目 [https://leetcode.com/problems/total-hamming-distance/][https_leetcode.com_problem

￡神魔★判官ぃ/ 2022年09月10日 07:14/ 0 赞/ 186 阅读

相关汉明距离

题目描述两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。注意： 0 ≤ x, y < 23

我就是我/ 2022年02月25日 08:48/ 0 赞/ 187 阅读