应用乘法原理统计集合元素组合个数 |周末学习

简介: 应用乘法原理统计集合元素组合个数 |周末学习

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 477. 汉明距离总和 ,难度为 中等


Tag : 「位运算」、「数学」


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


给你一个整数数组 nums,请你计算并返回 nums 中任意两个数之间汉明距离的总和。

 

示例 1:


输入:nums = [4,14,2]
输出:6
解释:在二进制表示中,4 表示为 0100 ,14 表示为 1110 ,2表示为 0010 。(这样表示是为了体现后四位之间关系)
所以答案为:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6
复制代码


示例 2:


输入:nums = [4,14,4]
输出:4
复制代码


提示:


1 <= nums.length <= $10^5$
0 <= nums[i] <= $10^9$
复制代码


按位统计



我们知道,汉明距离为两数二进制表示中不同位的个数,同时每位的统计是相互独立的。


即最终的答案为 \sum_{x = 0}^{31} calc(x)x=031calc(x),其中 calccalc 函数为求得所有数二进制表示中的某一位 xx 所产生的不同位的个数。


我们考虑某个 cacl(x)cacl(x) 如何求得:


事实上,对于某个 nums[i] 我们只关心在 nums 中有多少数的第 xx 位的与其不同,而不关心具体是哪些数与其不同,同时二进制表示中非 0011


这指导我们可以建立两个集合 s0s0s1s1,分别统计出 nums 中所有数的第 xx 位中 00 的个数和 11 的个数,集合中的每次计数代表了 nums 中的某一元素,根据所在集合的不同代表了其第 xx 位的值。那么要找到在 nums 中有多少数与某一个数的第 xx 位不同,只需要读取另外一个集合的元素个数即可,变成了 O(1)O(1) 操作。那么要求得「第 xx 位所有不同数」的对数的个数,只需要应用乘法原理,将两者元素个数相乘即可。


网络异常,图片无法展示
|


前面说到每位的统计是相对独立的,因此只要对「每一位」都应用上述操作,并把「每一位」的结果累加即是最终答案。


代码:


class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0;
        for (int x = 31; x >= 0; x--) {
            int s0 = 0, s1 = 0;
            for (int u : nums) {
                if (((u >> x) & 1) == 1) {
                    s1++;
                } else {
                    s0++;
                }  
            }
            ans += s0 * s1;
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:O(C * n)O(Cn)CC 固定为 3232
  • 空间复杂度:O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.477 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
7月前
|
Android开发 UED iOS开发
Harmony os next~UI开发与ArkUI框架
鸿蒙OS的UI开发基于ArkUI框架,采用声明式编程,简化开发流程。五大核心组件(Text、Button、List、Grid、Flex)助力高效布局,支持数据绑定与动态更新。事件响应机制灵敏,适合构建交互丰富的应用。实战技巧包括规范命名、样式复用和调试方法。掌握这些,轻松开发鸿蒙应用。下期预告:分布式开发,记得带上烤冷面!
235 0
|
12月前
|
人工智能 自然语言处理
通义灵码在Visual Studio2022中的实践
本文介绍了如何在Visual Studio 2022中安装和使用通义灵码。首先,在Visual Studio 2022中安装通义灵码插件,然后按照步骤完成安装和登录。最后,通过实操演示了通义灵码的三大功能:行级/函数级实时续写、自然语言生成代码和研发领域自由问答。希望读者能从中受益。
4928 4
|
12月前
|
JavaScript
Threejs实现PMD模型眨眼说话等功能
这篇文章详细介绍了如何在Three.js中实现PMD模型的眨眼和说话等动态效果,通过控制模型的关键帧来模拟面部表情的变化。
334 0
Threejs实现PMD模型眨眼说话等功能
|
应用服务中间件 Linux 网络安全
windows+linux环境下nginx部署环境
windows+linux环境下nginx部署环境
240 1
|
12月前
|
缓存 Ubuntu 网络协议
ubuntu ifconfig命令找不到
综上所述,面对 `ifconfig`缺失的问题,用户应首先考虑使用替代命令或通过安装额外软件包来解决,同时注意权限管理和环境变量的正确配置。通过这些策略,可以确保在Ubuntu系统中高效、无障碍地管理网络配置。
551 0
|
数据可视化 PyTorch Serverless
Python 性能分析的几个方法,找到你代码中的那个她
我们在编写了一个脚本在笔记本上处理一些数据,然后去喝杯咖啡或者上了个厕所,15分钟后回来时发现进度才完成不到10%。 我们的脑袋里面就会发问:为什么这么慢?究竟是在哪个部分是慢的?是读取数据、处理数据还是保存数据?如何让它变快?它真的很慢吗? 有了这个疑问我们尝试去解决这个问题,下面我们介绍几个 python 性能分析的工具。
|
关系型数据库 MySQL Shell
Mac安装Mysql(图文解说详细版)
Mac安装Mysql(图文解说详细版)
Mac安装Mysql(图文解说详细版)
|
监控 数据可视化 项目管理
PMP考试技巧(一)
PMP考试技巧
245 1
|
Linux C语言 固态存储
Linux创建、删除文件和文件夹等操作命令
今天学习了几个命令,是创建、删除文件和文件夹的,在linux里,文件夹是目录,下面说下我学习的命令。 创建文件夹【mkdir】   一、mkdir命令使用权限     所有用户都可以在终端使用 mkdir 命令在拥有权限的文件夹创建文件夹或目录。     二、mkdir命令使用格式     格式:mkdir [选项] DirName     三、mkdir命令功能    
35661 1
|
人工智能
AI绘画——ControlNet扩展安装教程
AI绘画——ControlNet扩展安装教程
2334 0