算法的学习笔记—数组中只出现一次的数字(牛客JZ56)

在这里插入图片描述

img

😀前言
在数组中寻找只出现一次的两个数字是一道经典的问题,通常可以通过位运算来有效解决。本文将详细介绍这一问题的解法,深入解析其背后的思路。

🏠个人主页:尘觉主页

文章目录

  • 🥰数组中只出现一次的数字
    • 题目链接
    • 😊问题描述
    • ❤️‍🔥解题思路
    • 😀Java 实现
      • 复杂度分析
    • 😄总结

🥰数组中只出现一次的数字

题目链接

牛客网

😊问题描述

给定一个整型数组,其中除了两个数字以外,其他数字均出现两次,目标是找出这两个只出现一次的数字。以数组 nums 为例:[x, x, y, y, z, k],其中 x、y 出现两次,而 z 和 k 各自只出现一次。

❤️‍🔥解题思路

  1. 利用异或运算

    • 异或运算的性质是相同的数字异或为 0,0 与任意数字异或的结果为该数字本身。根据这个性质,我们可以对数组中的所有元素进行异或操作。最终得到的结果将是这两个只出现一次的数字的异或结果。
    • 举个例子,对于数组 numsx ^ x ^ y ^ y ^ z ^ k = 0 ^ 0 ^ z ^ k = z ^ k
  2. 分离这两个数字

    • 由于 zk 是不同的,z ^ k 的结果必然是一个非零的值。我们需要找到 zk 在二进制表示上的一个不同的位。
    • 我们可以通过 diff = (z ^ k) & -(z ^ k) 来找到 diff,其中 diff 表示 zk 在二进制中最右侧为 1 的位。这个位的存在可以将数组中的数字分为两类,分别与 diff 进行异或运算。
  3. 遍历数组分组异或

    • 再次遍历数组,根据与

      diff
      

      的异或结果将数字分为两组:

      • 如果 num & diff == 0,则将 num 与第一个结果变量(如 res[0])进行异或。
      • 否则,将 num 与第二个结果变量(如 res[1])进行异或。
    • 最终,res[0]res[1] 就是我们要找的两个数字。

😀Java 实现

以下是用 Java 语言实现的完整代码:

public class Solution {
    public int[] FindNumsAppearOnce(int[] nums) {
        int[] res = new int[2];
        int diff = 0;

        // 第一步:计算所有数字的异或结果
        for (int num : nums) {
            diff ^= num;
        }

        // 第二步:获取 diff 最右侧的 1
        diff &= -diff;

        // 第三步:分组异或
        for (int num : nums) {
            if ((num & diff) == 0) {
                res[0] ^= num;  // 与 diff 的结果为 0 的数
            } else {
                res[1] ^= num;  // 与 diff 的结果不为 0 的数
            }
        }

        // 可选步骤:为了返回时更有序,可以选择排序
        if (res[0] > res[1]) {
            swap(res);
        }
        return res;
    }

    private void swap(int[] nums) {
        int t = nums[0];
        nums[0] = nums[1];
        nums[1] = t;
    }
}

复杂度分析

  • 时间复杂度:O(n),需要遍历数组两次。
  • 空间复杂度:O(1),只使用了常量空间来存储结果。

😄总结

通过以上的步骤,我们可以高效地找出数组中只出现一次的两个数字。利用异或运算的特性,我们能够将问题转化为位运算,简化了复杂度。这种思路不仅适用于本题,也为解决类似的问题提供了重要的思路。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

img

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

rtsp的2种收流模式

rtsp协商成功以后就是rtp收流,又分为两种模式:rtp over rtsp(tcp)和rtp over udp。 1.rtsp over rtsp 这个现在一般都叫TCP,它的特点是rtsp服务端和客户端是共用一个tcp链接,也就是说rtsp协议报文、rtp包、rtcp数据都是通过这一个链接来交互…

合约门合同全生命周期管理系统:企业合同管理的数字化转型之道

合约门合同全生命周期管理系统:企业合同管理的数字化转型之道 1. 引言 在现代企业中,合同管理已经不再是简单的文件存储和审批流程,而是企业合规性、风险管理和业务流程的关键环节之一。随着企业规模的扩大和合同数量的增加,传统…

第二单元历年真题整理

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 参考答案 1. A 2. A 3. A 4. D 5. D 6. D 解析: 栈和队列是两个不一样的结构,不能放在一起表示 7. B 8. C 解析: S --> A0 | B1 --> (S1 | 1) 0 | (S0 | 0)1 --> S10 | 10 | S…

51单片机快速入门之 模拟 I2C 用精准中断来控制

51单片机快速入门之 模拟 I2C 用精准中断来控制 首先复习一下51单片机快速入门之定时器和计数器(含中断基础) 再看看之前的I2C操作 51单片机快速入门之 IIC I2C通信 定时器/计数器是51单片机中用于实现精确延时的硬件资源。通过配置定时器的初始值和工作模式,可以…

Unable to open nested entry ‘********.jar‘ 问题解决

今天把现网版本的task的jar拖回来然后用7-zip打开拖了一个jar进去替换mysql-connector-java-5.1.47.jar 为 mysql-connector-java-5.1.27.jar 启动微服务的时候就报错下面的 Exception in thread "main" java.lang.IllegalStateException: Failed to get nested ar…

《Python游戏编程入门》注-第2章2

《Python游戏编程入门》的“2.2.5 绘制线条”中提到了通过pygame库绘制线条的方法。 1 相关函数介绍 通过pygame.draw模块中的line()函数来绘制线条,该函数的格式如下所示。 line(surface, color, start_pos, end_pos, width1) -> Rect 其中,第一…

开源限流组件分析(二):uber-go/ratelimit

文章目录 本系列漏桶限流算法uber的漏桶算法使用mutex版本数据结构获取令牌松弛量 atomic版本数据结构获取令牌测试漏桶的松弛量 总结 本系列 开源限流组件分析(一):juju/ratelimit开源限流组件分析(二):u…

部署前后端分离若依项目--CentOS7宝塔版

准备: CentOS7服务器一台 通过网盘分享的文件:CentOS 7 h 链接: https://pan.baidu.com/s/17DF8eRSSDuj9VeqselGa_Q 提取码: s7x4 大家有需要可以下载这个,密码61 若依前端编译后文件 通过网盘分享的文件:ruoyi-admin.jar 链…

生信软件39 - GATK最佳实践流程重构,提高17倍分析速度的LUSH流程

1. LUSH流程简介 基因组测序通常用于分子诊断、分期和预后,而大量测序数据在分析时间方面提出了挑战。 对于从FASTQ到VCF的整个流程,LUSH流程在非GVCF和GVCF模式下都大大降低了运行时间,30 X WGS数据耗时不到2 h,从BAM到VCF约需…

【计网】UDP Echo Server与Client实战:从零开始构建简单通信回显程序

目录 前言: 1.实现udpserver类 1.1.创建udp socket 套接字 --- 必须要做的 socket()讲解 代码实现:​编辑 代码讲解: 1.2.填充sockaddr_in结构 代码实现: 代码解析: 1.3.bind sockfd和…

linux中级wed服务器(https搭建加密服务器)

一。非对称加密算法: 公钥:公共密钥,开放 私钥:私有密钥,保密 1.发送方用自己的公钥加密,接受方用发送方的私钥解密:不可行 2.发送方用接受方的公钥加密,接受方用自己的私钥解密…

ffmpeg视频滤镜: 色温- colortemperature

滤镜简述 colortemperature 官网链接 》 FFmpeg Filters Documentation 这个滤镜可以调节图片的色温,色温值越大显得越冷,可以参考一下下图: 咱们装修的时候可能会用到,比如选择灯还有地板的颜色的时候,选暖色调还是…

【论文+源码】基于spring boot的垃圾分类网站

创建一个基于Spring Boot的垃圾分类网站涉及多个步骤,包括环境搭建、项目创建、数据库设计、后端服务开发、前端页面设计等。下面我将引导您完成这个过程。 第一步:准备环境 确保您的开发环境中安装了以下工具: Java JDK 8 或更高版本Mav…

Unity URP ShaderGraph 基本设置

先简单了解一下各种渲染管线之间的区别 Unity 从 2019.3 版本开始正式支持通用渲染管线(URP,Universal Render Pipeline)。URP 是轻量渲染管线(LWRP,Lightweight Render Pipeline)的升级和重命名版本&…

【解决】使用Hypermark将Markdown文件转化为HTML文件

写在前面: 如果文章对你有帮助,记得点赞关注加收藏一波,利于以后需要的时候复习,多谢支持! 文章目录 一、文件准备(一)HTML模板文件(二)MD文件夹和储存文件夹 二、文件转…

COSCon'24 志愿者招募令:共创开源新生活!

亲爱的开源爱好者们, 第九届中国开源年会(COSCon24)即将在北京中关村国家自主创新示范区会议中心于2024年11月2日至3日隆重举行。今年的主题是“Open Source, Open Life|开源新生活”,旨在探索开源技术如何在各个领域推…

日常记录,使用springboot,vue2,easyexcel使实现字段的匹配导入

目前的需求是数据库字段固定,而excel的字段不固定,需要实现excel导入到一个数据库内。 首先是前端的字段匹配,显示数据库字段和表头字段 读取表头字段: 我这里实现的是监听器导入,需要新建一个listen类。 读Excel …

uniApp 加载google地图 并规划路线

uniApp 加载google地图 并规划路线 备注:核心代码实例 备注: 打开谷歌地图失败的话 参考google开发文档 https://developers.google.com/maps/documentation/urls/ios-urlscheme?hlzh-cn#swift核心代码 mounted() {this.loadGoogleMapsScript(); }, methods: {//加载loadGo…

AI服务器HBA卡的国产PCIe4.0/5.0 switch信号完整性设计与实现,支持定制(二)

表 2 展示了 PCB 板所选介质材料 PSR4000AUS703 , &#xff3…

解决Redis缓存穿透(缓存空对象、布隆过滤器)

文章目录 背景代码实现前置实体类常量类工具类结果返回类控制层 缓存空对象布隆过滤器结合两种方法 背景 缓存穿透是指客户端请求的数据在缓存中和数据库中都不存在,这样缓存永远不会生效,这些请求都会打到数据库 常见的解决方案有两种,分别…