477. 汉明距离总和|Java 刷题打卡

477. 汉明距离总和|Java 刷题打卡

技术杂谈小彩虹2021-07-14 10:57:38100A+A-

本文正在参加「Java主题月 - Java 刷题打卡」,详情查看 活动链接

一、题目描述

image.png

二、解题思路

leetcode每日一题,今天是汉明距离升级版。 昨天我们已经学会了计算汉明距离

1.逐位统计

如果我们两两计算一对数字的汉明距离,那时间复杂度为O(n^2logn).
那有没有复杂度更低的算法呢??
答案是可以的:

对于数组nums 中的某个元素 val,若其二进制的第 i 位为 1,我们只需统计 nums 中有多少元素的第 i 位为 0, 
即计算出了val 与其他元素在第 i 位上的汉明距离之和。具体地,若长度为n 的数组nums 的所有元素二进制的第i  
位共有 c 个 1,n−c个0,则些元素在二进制的第 i 位上的汉明距离之和为:
                    c⋅(n−c)

代码实现

class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < 30; ++i) {
            int c = 0;
            for (int val : nums) {
                c += (val >> i) & 1;
            }
            ans += c * (n - c);
        }
        return ans;
    }
}

时间复杂度分析

只需要统计n个数字的位1数,因此时间复杂度:

  • O(n⋅L) 其中L=30

空间复杂度分析

常数辅助空间,因此空间复杂度:

  • O(1)

不晓得我讲清楚了没有,请大家多多指教。
今日打卡结束!

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1

联系我们