Leetcode3020. 子集中元素的最大数量

Every day a Leetcode

题目来源:3020. 子集中元素的最大数量

解法1:哈希 + 枚举

用一个哈希表统计数组 nums 中的元素及其出现次数。

暴力枚举数组中的数,作为 x,然后不断看 x2,x4,⋯ 在数组中的个数。直到个数不足 2 个为止,退出循环。

注意模式的正中间的数字只取一个。如果最后 x 有一个,那么个数加一,否则个数减一。

注意特判 x=1 的情况。

代码:

/** @lc app=leetcode.cn id=100206 lang=cpp** [100206] 子集中元素的最大数量*/// @lc code=start
class Solution
{
public:int maximumLength(vector<int> &nums){// 特判if (nums.empty())return 0;unordered_map<long long, int> cnt;for (int &num : nums)cnt[num]++;// 特判 x=1 的情况int ans = cnt[1] - (cnt[1] % 2 == 0);cnt.erase(1);for (auto &[num, _] : cnt){int res = 0;long long x;for (x = num; cnt.contains(x) && cnt[x] > 1; x *= x)res += 2;if (cnt.contains(x))res++;elseres--;ans = max(ans, res);}return ans;}
};
// @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(nloglogU),其中 n 为数组 nums 的长度,U=max⁡(nums)。

空间复杂度:O(n)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/253446.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RabbitMQ-3.发送者的可靠性

发送者的可靠性 3.发送者的可靠性3.1.生产者重试机制3.2.生产者确认机制3.3.实现生产者确认3.3.1.开启生产者确认3.3.2.定义ReturnCallback3.3.3.定义ConfirmCallback 3.发送者的可靠性 首先&#xff0c;我们一起分析一下消息丢失的可能性有哪些。 消息从发送者发送消息&#…

B站UP主实时信息获取展示php源码

B站UP主实时数据展示系统 - PHP源码分享 想要实时追踪你心仪的B站UP主的最新动态吗&#xff1f;现在&#xff0c;你可以轻松获取并展示B站UP主的实时数据&#xff0c;包括粉丝数、作品数、头像、播放量等关键信息。 功能亮点&#xff1a; 实时更新&#xff1a;系统通过B站AP…

拿捏循环链表

目录&#xff1a; 一&#xff1a;单链表&#xff08;不带头单向不循环&#xff09;与循环链表&#xff08;带头双向循环&#xff09;区别 二&#xff1a;循环链表初始化 三&#xff1a;循环链表头插 四&#xff1a;循环链表尾插 五&#xff1a;循环链表头删 六&#xff1…

如何保持mac苹果电脑系统在最佳状态?不卡顿

苹果电脑一直以其卓越的性能和用户友好的操作系统而备受欢迎。然而电脑上的文件、应用程序和缓存可能会逐渐积累&#xff0c;导致性能下降。为了确保你的苹果电脑保持最佳状态&#xff0c;高效清理是至关重要的一步。在本文中&#xff0c;我们将分享一些如何清理苹果电脑更高效…

Sping Cloud Hystrix 参数配置、简单使用、DashBoard

Sping Cloud Hystrix 文章目录 Sping Cloud Hystrix一、Hystrix 服务降级二、Hystrix使用示例三、OpenFeign Hystrix四、Hystrix参数HystrixCommand.Setter核心参数Command PropertiesFallback降级配置Circuit Breaker 熔断器配置Metrix 健康统计配置Request Context 相关参数C…

基于spring boot实现邮箱发送和邮箱验证

目录 一、邮箱发送实现1. 开通邮箱服务2. 添加邮箱依赖3.添加配置4.添加邮箱通用类5. 测试类 二、邮箱验证实现1.添加依赖2. 添加配置3.添加controller4. 测试 项目地址: https://gitee.com/nssnail/springboot-email 一、邮箱发送实现 1. 开通邮箱服务 使用qq邮箱、163邮箱都…

[UI5 常用控件] 06.Splitter,ResponsiveSplitter

文章目录 前言1. Splitter1.1 属性 2. ResponsiveSplitter 前言 本章节记录常用控件Splitter,ResponsiveSplitter。主要功能是分割画面布局。 其路径分别是&#xff1a; sap.ui.layout.Splittersap.ui.layout.ResponsiveSplitter 1. Splitter 1.1 属性 orientation &#x…

【力扣】快乐数,哈希集合+快慢指针+数学

快乐数原题地址 方法一&#xff1a;哈希集合 定义函数getNext(n)&#xff0c;返回n的所有位的平方和。一直执行ngetNext(n)&#xff0c;最终只有2种可能&#xff1a; n停留在1。无限循环且不为1。 证明&#xff1a;情况1是存在的&#xff0c;如力扣的示例一&#xff1a; 接…

正点原子--STM32基本定时器学习笔记(1)

目录 1. 定时器概述 1.1 软件定时原理 1.2 定时器定时原理 1.3 定时器分类 1.4 定时器特性表 1.5 基本、通用、高级定时器的功能整体区别 2. 基本定时器简介 3. 基本定时器框图 时钟树分析 这部分是笔者对基本定时器的理论知识进行学习与总结&#xff01;主要记录学习…

【PyTorch][chapter 15][李宏毅深度学习][Neighbor Embedding-LLE]

前言&#xff1a; 前面讲的都是线性降维&#xff0c;本篇主要讨论一下非线性降维. 流形学习&#xff08;mainfold learning&#xff09;是一类借鉴了拓扑流行概念的降维方法. 如上图,欧式距离上面 A 点跟C点更近&#xff0c;距离B 点较远 但是从图形拓扑结构来看&#xff0c; …

算法学习——华为机考题库10(HJ64 - HJ69)

算法学习——华为机考题库10&#xff08;HJ64 - HJ69&#xff09; HJ64 MP3光标位置 描述 MP3 Player因为屏幕较小&#xff0c;显示歌曲列表的时候每屏只能显示几首歌曲&#xff0c;用户要通过上下键才能浏览所有的歌曲。为了简化处理&#xff0c;假设每屏只能显示4首歌曲&a…

C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码

一、莱文斯坦&#xff08;Levenshtein&#xff09; Vladimir I. Levenshtein 弗拉基米尔I列文施坦博士是纠错码理论的先驱&#xff0c;被称为俄罗斯编码理论之父。Levenshtein是莫斯科俄罗斯科学院Keldysh应用数学研究所的研究教授&#xff0c;他的贡献体现在消费者的日常生活中…

蓝桥杯刷题day08——完全日期

1、题目描述 如果一个日期中年月日的各位数字之和是完全平方数&#xff0c;则称为一个完全日期。 例如&#xff1a;2021年6月5日的各位数字之和为20216516&#xff0c;而16是一个完全平方数&#xff0c;它是4的平方。所以2021年6月5日是一个完全日期。 请问&#xff0c;从200…

vue对于安装依赖时不好习惯的反省

因为一个不好的习惯&#xff0c;我总是喜欢–save去安装依赖包&#xff0c;然后发现最后打包后的内容总是很大。就想着怎么能让包小一些&#xff0c;就发现我遗漏了vue安装依赖的一个小知识点 安装依赖的时候可以-s -d -g去安装&#xff0c;要根据使用的内容选择去安装&#xf…

人工智能 | 深度学习的进展

深度学习的进展 深度学习是人工智能领域的一个重要分支&#xff0c;它利用神经网络模拟人类大脑的学习过程&#xff0c;通过大量数据训练模型&#xff0c;使其能够自动提取特征、识别模式、进行分类和预测等任务。近年来&#xff0c;深度学习在多个领域取得了显著的进展&#…

【高阶数据结构】B-树详解

文章目录 1. 常见的搜索结构2. 问题提出使用平衡二叉树搜索树的缺陷使用哈希表的缺陷 3. B-树的概念4. B-树的插入分析插入过程分析插入过程总结 5. B-树的代码实现5.1 B-树的结点设计5.2 B-树的查找5.3 B-树的插入实现InsertKey插入和分裂测试 6. B-树的删除&#xff08;思想&…

Redis 命令大全

文章目录 启动与连接Key&#xff08;键&#xff09;相关命令String&#xff08;字符串&#xff09;Hash&#xff08;哈希&#xff09;List&#xff08;列表&#xff09;Set&#xff08;集合&#xff09;Sorted Set&#xff08;有序集合&#xff09;其他常见命令HyperLogLog&…

WordPress如何实现随机显示一句话经典语录?怎么添加到评论框中?

我们在一些WordPress网站的顶部或侧边栏或评论框中&#xff0c;经常看到会随机显示一句经典语录&#xff0c;他们是怎么实现的呢&#xff1f; 其实&#xff0c;boke112百科前面跟大家分享的『WordPress集成一言&#xff08;Hitokoto&#xff09;API经典语句功能』一文中就提供…

相机图像质量研究(6)常见问题总结:光学结构对成像的影响--对焦距离

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…

Spring Data Envers 数据审计实战

随着各行各业信息化发展&#xff0c;决策者们越来越意识到数据版本追踪的重要性&#xff0c;尤其是上市公司&#xff0c;数据对于他们尤为重要。考虑到研发成本&#xff0c;对重要表单数据支持页面级的修改历史查看、对所有业务数据支持DB级的版本查看是一个不错的选择。 对于…