• 售前

  • 售后

热门帖子
入门百科

php计算汉明间隔总和的实例讲授

[复制链接]
123456823 显示全部楼层 发表于 2021-8-14 14:45:57 |阅读模式 打印 上一主题 下一主题
两个整数的汉明距离指的是这两个数字的二进制数对应位差异的数量。
计算一个数组中,恣意两个数之间汉明距离的总和。
实例
  1. 输入: 4, 14, 2
  2. 输出: 6
  3. 解释:在二进制表示中,4表示为0100,14表示为1110,2表示为0010。(这样表示是为了体现后四位之间关系)
  4. 所以答案为:HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
复制代码
注意:
数组中元素的范围为从 0到 10^9。数组的长度不高出 10^4。
解题思绪
穷举两两组合的数量,然后累加汉明距离,这个是最简单直白的方案。
结果是大量数据的时间会超时,阶乘的数量太多。
  1. class Solution {
  2.     /**
  3.     * @param Integer[] $nums
  4.     * @return Integer
  5.     */
  6.     function totalHammingDistance($nums) {
  7.         $count = count($nums);
  8.         $sum = 0;
  9.         for ($i = 0; $i < $count - 1; $i++) {
  10.             for ($j = $i+1; $j < $count; $j++)
  11.             {
  12.                 $sum += $this->hm($nums[$i], $nums[$j]);
  13.             }
  14.         }
  15.         return $sum;
  16.     }
  17.    // 汉明距离方法
  18.      function hm($x, $y)
  19.     {
  20.         return substr_count(decbin($x ^ $y), '1');
  21.     }}
复制代码
思绪扩展:
解题思绪扩展
咱们常常会这样分析题目:最简单的状况 -> 通常的、复杂的状况。从前咱们是:遍历全部大概的两两组合。
如今咱们换一个角度看:如果int只有1位-> int有32位。leetcode
起首,如果 int 只有 1 位,即数组 nums 中的元素只有两种状况,0 大概 1,此时求汉明距离总和的步调以下:get
起首将数组分红两组,全 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)$。
可以大概看下面这个例子:
十进制 二进制
  1. 4: 0 1 0 0
  2. 14: 1 1 1 0
  3. 2: 0 0 1 0
  4. 1: 0 0 0 1
复制代码
先看末了一列,有三个 0 和一个 1,那么它们之间相互的汉明距离就是 3,即 1 和别的三个 0 分别的距离累加,而后在看第三列,累加汉明距离为 4,由于每一个 1 都会跟两个 0 产生两个汉明距离,同理第二列也是 4,第一列是 3。各列相互之间两两组合的汉明距离总和就是各列 0 的个数与 1 的个数之和,把各列汉明距离总和再累加就是题目所求的数组 nums 元素两两之间的汉明距离总和。
代码
  1. class Solution {
  2. /**
  3. * @param Integer[] $nums
  4. * @return Integer
  5. */
  6. function totalHammingDistance($nums) {
  7. $count = count($nums);
  8. $sum = 0;
  9. for($i = 0; $i < 32; $i++)
  10. {
  11. $tmpCount = 0;
  12. for($j = 0; $j < $count; $j++)
  13. $tmpCount += ($nums[$j] >> $i) & 1;
  14. }
  15. $sum += $tmpCount * ($count - $tmpCount);
  16. }
  17. return $sum;
  18. }
  19. }
复制代码
到此这篇关于php计算汉明距离总和的实例讲解的文章就介绍到这了,更多相干php计算汉明距离总和的方法内容请搜索草根技术分享从前的文章或继承欣赏下面的相干文章希望各人以后多多支持草根技术分享!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作