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

【LeetCode】剑指 Offer 56. 数组中数字出现的次数 p275 -- Java Version

1. 题目介绍(56. 数组中数字出现的次数)

面试题56.:数组中数字出现的次数, 一共分为两小题:

  • 题目一:数组中只出现一次的两个数字
  • 题目二:数组中唯一只出现一次的数字

2. 题目1:数组中只出现一次的两个数字

题目链接:https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

2.1 题目介绍

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n),空间复杂度是 O(1)

【测试用例】:
示例1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

【条件约束】:

限制

  • 2 <= nums.length <= 10000

2.2 题解 – 位运算(XOR)-- O(n)

时间复杂度O(n),空间复杂度O(1)

解题思路】:
该问题是问在一个数组中找出 两个只出现一次的数字 ,那么我们可以先从这个数组中 只有一个数字只出现了一次 开始考虑:

  • 首先我们可以想到 异或运算 的一个性质:任何一个数字异或它自己都等于0;也就是说,如果我们从头到尾依次异或数组中的每个数字,那么最终的结果刚好是那个只出现依次的数组,因为那些成对出现两次的数字全部在异或中抵消了(当然,这也是一个前提条件,要求 数组中的其它数字都是出现了两次,而不是三次或其他次,只能是 偶数次 才行)

……
既然,我们有了得到只出现一次数字的办法,那么我们就要想怎么求出两个只出现一次的数字:

  • 我们可以试着将 原数组分成两个子数组 ,使得每个子数组包含一个只出现一次的数字,而其它数字都承兑出现两次。只要能够这样拆分成两个数组,那么我们就可以按照前面的办法分别找出两个只出现一次的数字

……
实现策略】:

  1. 首先还是先进行无效输入的判断,判断数组长度 nums.length 是否小于等于 0,如果是,则说明是无效数据;
  2. 定义变量 exclusiveOr,获取数组中所有元素的异或结果(该结果可以等同于 数组中两个唯一只出现一次的数字 的异或结果);
  3. 我们可以根据这个异或结果(exclusiveOr),去寻找这两个数字是在哪一位开始不同的,即从低位到高位,第一个 Bit为1 的位置;
  4. 找到这个位置后,我们就可以根据这个位置进行分组了,我们将 该位为1 的数据分为一组,不为1 的分为一组,然后对其进行异或,最后剩下的数字就是我们要找到的两个数字了。
class Solution {// Solution1:异或分组和筛选public int[] singleNumbers(int[] nums) {// 无效输入判断if (nums.length <= 0) return null;// 将数组中所有元素进行异或int exclusiveOr = 0;for (int i = 0; i< nums.length; i++) {// 异或完成后,一样的会被抵消,只剩下不一样的两个数字,需要我们对其进行分组exclusiveOr ^= nums[i];}int indexBitIs1 = findFirstBitIs1(exclusiveOr);// 遍历数组并分组判断int[] res = new int[2];for (int j = 0; j < nums.length; j++) {if (isBit1(nums[j], indexBitIs1)) res[0] ^= nums[j];else res[1] ^= nums[j];}// 循环结束,返回结果return res;}// 从右向左寻找第一位为1的位数public int findFirstBitIs1(int num) {int indexFirstBitIs1 = 0;while ((num & 1) == 0 && (indexFirstBitIs1 < 32)) {num = num >> 1;indexFirstBitIs1++;}return indexFirstBitIs1;}// 判断输入的数字的indexBitIs1位是不是1public boolean isBit1(int num, int indexBitIs1) {num = num >> indexBitIs1;return (num & 1) != 0 ;}
}

代码简化:

class Solution {public int[] singleNumbers(int[] nums) {int x = 0, y = 0, n = 0, m = 1;for(int num : nums)               // 1. 遍历异或n ^= num;while((n & m) == 0)               // 2. 循环左移,计算 mm <<= 1;for(int num: nums) {              // 3. 遍历 nums 分组if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0else y ^= num;                // 4. 当 num & m == 0}return new int[] {x, y};          // 5. 返回出现一次的数字}
}

3. 题目2:

题目链接:https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

3.1 题目介绍

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

【测试用例】:
示例1:

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

示例2:

输入:nums = [9,1,7,9,7,9,7]
输出:1

【条件约束】:

限制

  • 1 <= nums.length <= 10000
  • 1 <= nums[i] < 2^31

3.2 题解 – 位运算 – O(n)

时间复杂度O(n),空间复杂度O(1)

解题思路】:
因为三个相同的数字的异或结果还是该数字,因此我们在这里就不能再使用异或运算解决该问题了,不过我们还是可以沿用位运算的思路:

  1. 如果一个数字出现三次,那么它的二进制表示的每一位(0 或者 1)也出现三次;
  2. 如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被 3 整除;
  3. 我们把数组中所有数字的二进制表示的每一位都加起来,如果某一位的和能被 3 整除,那么那个只出现一次的数字二进制表示中对应的那一位是 0;否则就是 1.

……
这种解法的时间效率是 O(n),我们需要一个长度为 32 的辅助数组存储二进制表示的每一位的和。当然,除此之外,还有其它解法:

  1. 排序数组中找到只出现一次的数字,但排序需要额外的 O(nlogn) 的时间;
  2. 用一个哈希表来记录数组中每个数字出现的次数,但这个哈希表需要额外的 O(n) 的空间;
  3. 有限状态自动机:各二进制位的 位运算规则相同 ,因此只需考虑一位即可。如下图所示,对于所有数字中的某二进制位 1 的个数,存在 3 种状态,即对 3 余数为 0,1,2 ;该方法虽然效率较高,但也较难理解
class Solution {// Solution1:位运算public int singleNumber(int[] nums) {// 定义辅助数组 counts,用来存储二进制表示的每一位的和int[] counts = new int[32];// 循环遍历数组中的所有数for(int num : nums) {// 将该数的32位分别存入数组for(int j = 0; j < 32; j++) {counts[j] += num & 1;num = num >> 1;}}int res = 0, m = 3;for(int i = 0; i < 32; i++) {// 移位处理res <<= 1;// 如果 某一位的和能被 3 整除,那么那个只出现一次的数字// 二进制表示中对应的哪一位是0;否则就是1res |= counts[31 - i] % m;}return res;}
}

有限状态自动机:
在这里插入图片描述

class Solution {public int singleNumber(int[] nums) {int ones = 0, twos = 0;for(int num : nums){ones = ones ^ num & ~twos;twos = twos ^ num & ~ones;}return ones;}
}

4. 参考资料

[1] 剑指 Offer 56 - I. 数组中数字出现的次数(位运算,清晰图解)

相关文章:

【LeetCode】剑指 Offer 56. 数组中数字出现的次数 p275 -- Java Version

1. 题目介绍&#xff08;56. 数组中数字出现的次数&#xff09; 面试题56.&#xff1a;数组中数字出现的次数&#xff0c; 一共分为两小题&#xff1a; 题目一&#xff1a;数组中只出现一次的两个数字题目二&#xff1a;数组中唯一只出现一次的数字 2. 题目1&#xff1a;数组中…...

Zookeeper集群 + Fafka集群

目录 第一章Zookeeper 概述 1.1.Zookeeper 定义 1.2.Zookeeper 工作机制 1.3.Zookeeper 特点 1.4.Zookeeper 数据结构 1.5.Zookeeper 应用场景 1.6.Zookeeper 原理之选举机制 1.7.部署 Zookeeper 集群 总结 第二章消息队列概述 2.1消息队列需求原因 2.2消息队列的优…...

全国青少年电子信息智能创新大赛(复赛)python·模拟四卷

目录 一、编程题 答案解析如下: 下载文档打印做题: 全国青少年电子信息智能创新大赛(复赛)python模拟四卷 一、编程题 第一题:描述 班上有学生若干名,给出每名学生的年龄《整数),求班上所有学生的平均年龄,保留到小数点后两企 输入 第一行有一个整数n (1<= n...

Redis - 介绍与使用场景

简介 Redis 的全称是 Remote Dictionary Server&#xff0c;是一个使用 C 语言编写的、开源的&#xff08;BSD 许可&#xff09;高性能非关系型&#xff08;NoSQL&#xff09;的键值对数据库。 Redis 的数据是存储在内存中的&#xff0c;所以读写速度非常快&#xff0c;被广泛…...

Spark SQL实战(07)-Data Sources

1 概述 Spark SQL通过DataFrame接口支持对多种数据源进行操作。 DataFrame可使用关系型变换进行操作&#xff0c;也可用于创建临时视图。将DataFrame注册为临时视图可以让你对其数据运行SQL查询。 本节介绍使用Spark数据源加载和保存数据的一般方法&#xff0c;并进一步介绍…...

Django DRF - 权限Permissions

权限Permissions 权限控制可以限制用户对于视图的访问和对于具体数据对象的访问。 在执行视图的dispatch()方法前&#xff0c;会先进行视图访问权限的判断在通过get_object()获取具体对象时&#xff0c;会进行对象访问权限的判断 1.提供的权限 AllowAny 允许所有用户IsAuth…...

二叉树(OJ)

单值二叉树&#xff08;力扣&#xff09; ---------------------------------------------------哆啦A梦的任意门------------------------------------------------------- 我们来看一下题目的具体要求&#xff1a; 既然我们都学了二叉树了&#xff0c;我们就应该学会如何去…...

mysql中增删改成的练习

文章目录一、表的创建1.student表的数据2、课程表的数据course3、学生成绩表的数据二、操作序列1、查询计算机系cs的全体学生学号、姓名和性别2、检索选修了课程号为2的学生号和姓名3、检索至少选修了三门课以上的学生号4、检索选修了全部课程的学生5、在原表的基础上创建一个视…...

谈一谈Java的ThreadLocal

目录 先说原理&#xff1a; 再上代码&#xff1a; 运行结果&#xff1a; 先说原理&#xff1a; ThreadLocal 是一个本地线程副本变量工具类&#xff0c;它可以在每个线程中创建一个副本变量&#xff0c;每个线程可以独立地修改自己的副本变量&#xff0c;而不会影响其他线程…...

边缘检测与阈值分割

Canny [1] Canny Edge Detection. https://docs.opencv.org/3.4/da/d22/tutorial_py_canny.html [2] OpenCV Edge Detection ( cv2.Canny ). https://pyimagesearch.com/2021/05/12/opencv-edge-detection-cv2-canny/ 由John F. Canny提出 1、由于边缘检测容易受噪声影响&…...

QQ空间无敌装逼,复制下面的任一代码粘贴即可出现意想不到的图案。

复制下面的任一代码粘贴即可出现意想不到的图案。 打赏代码&#xff1a; [em]e10033[/em]{uin:123,nick: 打赏了你一个冰淇淋,who:1} [em]e10033[/em] 打赏了100000000000.00元红包 [em]e10011[/em] 赞代码:{uin:0000,nick: xx、xx、xx、xx、xx、xx、xx、xx、xx、xx、xx、x…...

必看!总结5种JavaScript异步解决方案

1.回调 回调简单地理解为一个函数作为参数传递给另一个函数&#xff0c;回调是早期最常用的异步解决方案之一。 回调不一定是异步的&#xff0c;也不直接相关。 举个简单的例子&#xff1a; function f1(cb) {setTimeout(() > {cb && cb();}, 2000); }f1(() >…...

JUC并发编程高级篇第四章之ThreadLocal(人手一份,天下安)

文章目录1、ThreadLocal的简介1.1、常见的面试题(也是本次的讲解的内容&#xff09;1.2、什么是ThreadLocal1.3、ThreadLocal的所用1.4、没有出现ThreadLocal前后的变化1.5、ThreadLocal代码示例1.6、阿里巴巴对ThreadLocal的使用要求1.7、ThreadLocal的源码分析2、ThreadLocal…...

dump 定位分析

在缺少pdb的时候如何分析dump&#xff1f; windbgidaWindbg定位崩溃位置 通过windbg打开dump&#xff0c;并且分析dump !analyze -v 分析&#xff1a; 分析dump&#xff1a; !analyze -v错误原因&#xff1a;读取空指针错误线程&#xff1a;00001e04&#xff0c;可通过命令…...

(十二)排序算法-插入排序

1 基本介绍 1.1 概述 插入排序属于内部排序法&#xff0c;是对于欲排序的元素以插入的方式找寻该元素的适当位置&#xff0c;以达到排序的目的。 插入排序的工作方式非常像人们排序一手扑克牌一样。开始时&#xff0c;我们的左手为空并且桌子上的牌面朝下。然后&#xff0c;…...

elasticsearch 认知

1.大数据领域需要解决以下三个问题 如何存储数据 传统的关系数据库&#xff08;MySQL、Oracle、和Access等&#xff09;主导了20世纪的数据存储模式&#xff0c;但当数据量达到太字节级&#xff0c;甚至拍字节级时&#xff0c;关系型数据库表现出了难以解决的瓶颈问题。为了解决…...

《人体地图》笔记

《人体地图》 坂井建雄 著 孙浩 译 腹部通向大腿的隧道 腹部与大腿的分界点是大腿根部&#xff0c;即是腹股沟。 腹壁肌肉连结在腹股沟韧带上&#xff0c;腹壁肌肉包括三层&#xff0c;分别为腹外斜肌、腹内斜肌和腹横肌&#xff0c;每块肌肉都有一个张开的小孔&#xff0c;…...

java基础集合面试题

什么是集合 集合就是一个放数据的容器&#xff0c;准确的说是放数据对象引用的容器 集合类存放的都是对象的引用&#xff0c;而不是对象的本身 集合类型主要有3种&#xff1a;set(集&#xff09;、list(列表&#xff09;和map(映射)。 集合的特点 集合的特点主要有如下两点&…...

Vue学习-Vue入门

Vue学习 一、Vue入门 1、 引入Vue Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套用于构建用户界面的渐进式框架。与其它大型框架不同的是&#xff0c;Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层&#xff0c;不仅易于上手&#xff0c;还便于与第三方库…...

【项目】bxg基于SaaS的餐掌柜项目实战(2023)

基于SaaS的餐掌柜项目实战 餐掌柜是一款基于SaaS思想打造的餐饮系统&#xff0c;采用分布式系统架构进行多服务研发&#xff0c;共包含4个子系统&#xff0c;分别为平台运营端、管家端&#xff08;门店&#xff09;、收银端、小程序端&#xff0c;为餐饮商家打造一站式餐饮服务…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...