大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章主要介绍“PHP怎么计算汉明距离总和”,在日常操作中,相信很多人在PHP怎么计算汉明距离总和问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”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; } }
到此,关于“PHP怎么计算汉明距离总和”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!