• 技术文章 >PHP >PHP教程

    php计算汉明距离总和的方法

    小妮浅浅小妮浅浅2021-07-08 16:54:51原创320

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

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

    实例

    输入: 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');
     
        }}

    以上就是php计算汉明距离总和的方法,希望对大家有所帮助。更多php学习指路:php教程

    本文转载于何晓东的博客,如有侵犯联系作者修改。

    专题推荐:php计算汉明距离
    品易云
    上一篇:php使用array_diff去除元素 下一篇:php数据流中第K大元素的计算方法

    相关文章推荐

    • php桥接模式的作用• php安装grpc扩展的方法• php引用的使用注意• php引用返回如何理解• php变量如何声明• php变量如何命名• php变量的引用赋值使用• php中的四种标量类型• php变量中的两种复合类型• php变量有哪些特殊类型• php定义常量方法的区别• php常量和变量的不同• php中DateTime的错误处理• php中unset函数的使用• php使用array_diff去除元素

    全部评论我要评论

  • 取消发布评论
  • 

    Python学习网