[LeetCode 477]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
。来源:力扣(LeetCode)
链接:477. Total Hamming Distance
穷举两两组合的数量,然后累加汉明距离,这个是最简单直白的方案。
结果是大量数据的时候会超时,阶乘的数量太多。
代码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,此时求汉明距离总和的步骤如下:
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;
}
}
参考链接
477. 汉明距离总和最后恰饭 阿里云全系列产品特惠购买,中小企业上云最佳选择
特别申明:本文内容来源网络,版权归原作者所有,如有侵权请立即与我们联系(cy198701067573@163.com),我们将及时处理。
php介绍
PHP即“超文本预处理器”,是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言,与C语言类似,是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习,使用广泛,主要适用于Web开发领域。
上一篇: php读取mysql数据输出乱码怎么办