当前位置: 首页 > news >正文

位运算(6)_只出现一次的数字 II

个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

位运算(6)_只出现一次的数字 II

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌

目录

温馨提示:

1. 题目链接 :

2. 题目描述 :

3. 解法(位运算) :

    算法思路 :

    代码展示 :

    结果分析 :


温馨提示:

本文的算法题需要一些位运算知识的基础,如果大家还不是很了解的话,可以先去看下面的博客:
位运算(1)_常见位运算总结-CSDN博客

1. 题目链接 :

OJ链接: 只出现一次的数字 II

2. 题目描述 :

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

(也就是时间复杂度为O(N),空间复杂度为O(1))

示例 1:

输入:nums = [2,2,3,2]
输出:3

示例 2:

输入:nums = [0,1,0,1,0,1,99]
输出:99

提示:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • nums 中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次

3. 解法(位运算) :

    算法思路 :

设要找的数位ret.

由于整个数组中,需要找的元素只出现了[一次],其余的数都出现了三次,因此我们可以根据所有数的[某一个比特位]的总和%3的结果,快速定位到ret的[一个比特位上]的值是0还是1.

这样我们通过ret的每一个比特位上的值,就可以将ret给还原出来.

    代码展示 :

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i < 32; i++){int sum = 0;for(auto ch : nums)if(((ch >> i) & 1) == 1) sum++;if(sum % 3) ret |= 1 << i;}return ret;}
};

    整体思路:
    位操作 : 利用位操作和位的统计方法来解决问题。每个数字都是由 32 位组成,遍历每一位并统计所有数字在该位上为 1 的次数。

    模运算 : 通过 sum % 3 来确定在这个位上是否只出现了一次的数字。如果该位的 1 的出现次数不为 3,则该位的值应该在结果中保留。

 

 

    结果分析 :

时间复杂度:

外层循环遍历 32 位:O(32), 也就是 O(1)。
内层循环遍历数组 nums,假设数组的长度为 n,则内层的复杂度为 O(n)。
总的时间复杂度为 O(n)。
空间复杂度 :

只使用了常数级别的额外空间(ret, sum, 和循环变量),所以空间复杂度为 O(1)。

相关文章:

位运算(6)_只出现一次的数字 II

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 位运算(6)_只出现一次的数字 II 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 …...

C#的Socket编程细节

目录 Socket中的Accept 步骤1&#xff1a;创建并绑定服务端套接字 步骤2&#xff1a;接受连接请求 步骤3&#xff1a;与客户端通信 步骤4&#xff1a;关闭套接字 注意事项 Socket中的Connected 使用Connected属性 客户端检查连接状态 服务端检查连接状态 注意事项 S…...

python三局两胜游戏

分为以下步骤实现这个功能 1、猜拳 2、机器产生数值 3、人去猜数字&#xff0c;定义剪刀石头布 4、控制机器产生&#xff0c;123程序运行的时候可能会出现一点玄学问题&#xff0c;就是&#xff0c;提示n1这一行不符合pep8然后报错&#xff0c;不用管&#xff0c;运行就可以&am…...

java:brew安装rabbitmq以及简单示例

什么是消息队列mq 可以看我之前写的这篇 消息队列MQ rabbitmq简介 RabbitMQ是由erlang语言开发&#xff0c;基于AMQP&#xff08;Advanced Message Queue 高级消息队列协议&#xff09;协议实现的消息队列&#xff0c;它是一种应用程序之间的通信方法&#xff0c;消息队列在…...

基于单片机跑步机控制系统设计

** 文章目录 前言概要功能设计设计思路 软件设计效果图 程序文章目录 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师&#xff0c;一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对…...

【架构】efk日志监控

文章目录 一、EFK组件及其功能二、EFK日志监控的工作流程三、EFK日志监控的优势四、EFK日志监控的应用场景 推荐阅读 EFK日志监控是一种高效的日志管理解决方案&#xff0c;由Elasticsearch、Fluentd&#xff08;或Logstash&#xff09;和Kibana三个开源工具组成。以下是对EFK日…...

亚信安全发布第34期《勒索家族和勒索事件监控报告》

本周态势快速感知 本周全球共监测到勒索事件91起&#xff0c;近三周勒索事件数量较为稳定。从整体上看&#xff0c;Ransomhub是影响最严重的勒索家族&#xff1b;Play和ElDorado恶意家族也是两个活动频繁的恶意家族&#xff0c;需要注意防范。本周&#xff0c;土耳其公司巴克皮…...

如何在实际应用中使用回溯算法解决问题?

如何在实际应用中使用回溯算法解决问题? 回溯算法是一种强大的问题解决方法,它通过尝试不同的选择并在遇到不可行的情况时回退,以找到满足特定条件的解决方案。在实际应用中,回溯算法可以用于解决各种复杂的问题。本文将介绍如何在实际应用中使用回溯算法,并通过一些案例…...

9. 正则表达式

编程工具和技术是以一种混乱、进化的方式生存和传播的。获胜的并不总是最好或最杰出的工具&#xff0c;而是那些在合适的利基市场中发挥足够好的功能&#xff0c;或者恰好与另一项成功的技术相结合的工具。 在本章中&#xff0c;我将讨论这样一种工具--正则表达式。正则表达式是…...

初始C++模板

1.泛型编程 1.1什么事泛型编程 在学习C语言时&#xff0c;我们时常会有这样的烦恼&#xff1a; 在针对每一种不同的类型变量进行函数传参或者是运算处理时&#xff0c;我们总是编写不同的函数或者是进行不同的处理&#xff0c;才能达到目的&#xff0c;这时&#xff0c;我们…...

建投数据自主研发相关系统获得欧拉操作系统及华为鲲鹏技术认证书

近日&#xff0c;经欧拉生态创新中心和华为技术有限公司测评&#xff0c;建投数据自主研发的投资项目管理系统、全面风险管理信息系统、商业不动产业务系统&#xff0c;完成了基于欧拉操作系统openEuler 22.03、华为鲲鹏Kunpeng 920&#xff08;Taisha 200&#xff09;的兼容性…...

node启动websocket保持后台一直运行

在 Node.js 中启动一个 WebSocket 服务器并使其在后台持续运行&#xff0c;你可以使用几种方法。下面是一种常见的方法&#xff0c;通过创建一个简单的 WebSocket 服务器并使用 node 命令直接运行它&#xff0c;同时确保它在后台运行。 1. 创建 WebSocket 服务器 首先&#x…...

CSS画出三角形的做法

引言&#xff1a; 在网页中&#xff0c;会有三角形的出现&#xff0c;我们脑海里会有很多想法&#xff0c;如何去实现他们&#xff0c;我来提供一种比较好玩的做法。 方法&#xff1a; 我们实现一个三角形&#xff0c;当然可以使用精灵图、或者iconfont的做法&#xff0c;这…...

web开发(1)-基础

这是对b站课程的总结&#xff0c;后续可能会继续更 01 前后端分离介绍_哔哩哔哩_bilibili01 前后端分离介绍是Web应用开发-后端基础-基于Springboot框架的第1集视频&#xff0c;该合集共计29集&#xff0c;视频收藏或关注UP主&#xff0c;及时了解更多相关视频内容。https://w…...

python程序操作Windows系统中的软件如word等(是否可以成功操作待验证)

一、python打开word软件 在 Python 中可以使用python-docx库来操作 Word 文档&#xff0c;但如果你的需求是直接打开 Word 软件&#xff0c;你可以使用os模块和subprocess模块来实现。以下是示例代码&#xff1a; import os import subprocessdef open_word():word_path rC:…...

人工智能发展历程

发展历程 人工智能的发展可以追溯到20世纪30年代&#xff0c;当时数理逻辑的形式化和智能可计算思想开始构建计算与智能的关联概念。1943年&#xff0c;美国神经科学家麦卡洛克和逻辑学家皮茨共同研制成功了世界上首个人工神经网络模型——MP模型&#xff0c;这为现代人工智能…...

Flutter路由

路由作为一种页面切换的能力&#xff0c;非常重要。Flutter 中路由管理有几个重要的点。 Navigator 1.0&#xff1a;Flutter 早期路由系统&#xff0c;侧重于移动端 &#xff0c;命令式编程风格&#xff0c;使用 Navigator.push() 和 Navigator.pop() 等方法来管理路由栈。 N…...

css预处理器less

CSS预处理器Less教程 CSS预处理器是一种扩展CSS功能的工具&#xff0c;它允许开发者使用变量、嵌套规则、混合&#xff08;Mixins&#xff09;、函数等高级特性&#xff0c;使CSS代码更加灵活、易于维护和扩展。Less是其中一种流行的CSS预处理器&#xff0c;它使用JavaScript编…...

WEB服务器——Tomcat

服务器是可以使用java完成编写&#xff0c;是可以接受页面发送的请求和响应数据给前端浏览器的&#xff0c;而在开发中真正用到的Web服务器&#xff0c;我们不会自己写的&#xff0c;都是使用目前比较流行的web服务器。 如&#xff1a;Tomcat 1. 简介 Tomcat 是一个开源的轻量…...

C++ STL(3)list

文章目录 一、list 详解1、内存管理2、常用操作3、迭代器erase()删除list中的元素 前言&#xff1a; C 标准模板库&#xff08;STL&#xff09;中的 list 容器是一种双向链表数据结构&#xff0c;它允许在常数时间内进行插入和删除操作&#xff0c;而无需重新分配整个容器或移动…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...