关于php:LeetCode-477PHP-计算汉明距离总和

32次阅读

共计 1601 个字符，预计需要花费 5 分钟才能阅读完成。

原文链接：何晓东博客

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

解题思路 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;
    }
}

参考链接