Leetcode137只出现一次的数字|| 及其拓展

简述:

虽然标题是这么描述的,但是我们不是一上来就解这道题,先看一下他的子题和扩展
子题:136. 只出现一次的数字 - 力扣(LeetCode)

扩展题:

所以我们由易到难,先来看第一道,只出现1次的数字,leetcode136

题目描述一:

解题思路一 :

Leetcode136 因为比较简单:就直接说了

在访问第 i 个数时,在不借助额外数据结构存储已访问的元素的情况下,我们无法判断当前访问的数有没有出现过。

那我们有没有方法通过某种运算让出现两次的数消失,最终的运算结果就是只出现一次的数。而位运算中的异或(XOR, 在Java中,用'^'表示) 可以。异或运算规则为:相同为 0,不同为 1。0 ^ 0 = 0; 1 ^ 1 = 0; 1 ^ 0 = 1;

让数组中的所有数异或,直接找到答案。

代码实现一:

	//思路:所有数字异或  ^   相同数字^为0,任何数字^0还是本身
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
        	res ^= nums[i];
        }
        return res;
    }

题目描述二:

 解题思路二:

这道题有两种解法,如下:

方法一:借用哈希表,key为出现的数字,value为出现数字的次数,借助这么一个结构,最后再遍历哈希表,即可找到答案,显然空间复杂度O(n),时间复杂度O(n)


方法二:不用哈希表

我们前面说过,在访问第 i 个数时,在不借助额外数据结构存储已访问的元素的情况下,我们无法判断当前访问的数有没有出现过。既然无法将所有数的二进制位进行异或运算,那能否做其他的运算?比如说“加法运算”,统计数组中所有的数在某个二进制位出现的次数,如果有二进制位出现的次数不是K的整数倍,说明有其他没有出现K次的数的贡献,而该数只有一个,就是答案。
这里的k,就是Leetcode137中的3   显然空间复杂度O(1),时间复杂度O(n)

代码实现二 :

	//美团要求:时间(n)  空间O(1)  意味着我们不能采用额外的数据结构来作答
    public int singleNumber(int[] nums,int k) {
        int res = 0;
        //整数由32位二进制表示   一般int 为4byte  32bit
        int numDigits = 32;
        for(int i = 0 ; i < numDigits; i++) {
        	int count = 0;
        	for(int j = 0; j < nums.length; j++) {
        		//统计数组中所有元素,从右向左数第 i 位 二进制上1的个数,>> 为右移操作
        		//为什么还要 & 1?  清除前面 1 的个数,防止影响当前这一位,也就是第i位的结果
        		count += (nums[j] >> i & 1) ; 
        	}
    		if(count % k == 1) {
    			//还原只出现1次的数 1 的分布, << 为左移
    			res |= (1 << i);
    		}
        }
        return res;
    }
    
    //这是Leetcode137的本题,上面为美团扩展的
    public int singleNumber(int[] nums) {
        int res = 0;
        int numDigits = 32;
        for(int i = 0 ; i < numDigits; i++) {
        	int count = 0;
        	for(int j = 0; j < nums.length; j++) {
        		//统计数组中所有元素,从右向左数第 i 位 二进制上1的个数,>> 为右移操作
        		//为什么还要 & 1?  清除前面 1 的个数,防止影响当前这一位,也就是第i位的结果
        		count += (nums[j] >> i & 1) ; 
        		if(count % 3 == 1) {
        			//还原只出现1次的数 1 的分布, << 为左移
        			res |= (1 << i);
        		}
        	}
        }
        return res;
    }

	
	//使用哈希表
	public int singleNumber(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            Integer value = entry.getValue();
            if (value == 1) {
                return entry.getKey();
            }
        }
        return nums[0];
    }

疑惑点 :

扩展题和Leetcode137 代码中,外面套了一层for循环,有些人可能会疑惑,为什么多了一层for,时间复杂度还是O(n)?

因为我的外面的for是固定的32次,只是比较大,但是是常数,所以说,就算拆开来看 也是 O(32) * O(n) = O(n),32这个常数可以省略,所以我们的时间复杂度还是O(n)

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

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

相关文章

leetcode 382.链表随机结点

1.题目要求: 2.题目代码: /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x)…

GaussDB Ustore存储引擎解读

目录 一、数据库存储引擎 二、GaussDB Ustore存储引擎 总结 本文将介绍GaussDB中的Ustore存储引擎&#xff0c;包括Ustore的设计背景、特点介绍和适用业务场景等。 一、数据库存储引擎 数据库的存储引擎负责在内存和磁盘上存储、检索和管理数据&#xff0c;确保每个节点的…

使用 Sortable.js 库 实现 Vue3 elementPlus 的 el-table 拖拽排序

文章目录 实现效果Sortable.js介绍下载依赖添加类名导入sortablejs初始化拖拽实例拖拽完成后的处理总结 在开发过程中&#xff0c;我们经常需要处理表格数据&#xff0c;并为用户提供便捷的排序方式。特别是在需要管理长列表、分类数据或动态内容时&#xff0c;拖拽排序功能显得…

机器学习是什么?AIGC又是什么?机器学习与AIGC未来科技的双引擎

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…

.net core 接口,动态接收各类型请求的参数

[HttpPost] public async Task<IActionResult> testpost([FromForm] object info) { //Postman工具测试结果&#xff1a; //FromBody,Postman的body只有rawjson时才进的来 //参数为空时&#xff0c;Body(form-data、x-www-form-urlencoded)解析到的数据也有所…

探索Unity:从游戏引擎到元宇宙体验,聚焦内容创作

unity是实时3D互动内容创作和运营平台&#xff0c;包括游戏开发、美术、建筑、汽车设计、影视在内的所有创作者&#xff0c;借助Unity将创意变成现实。提供一整套完善的软件解决方案&#xff0c;可用于创作、运营和变现任何实时互动的2D和3D内容&#xff0c;支持平台包括手机、…

构造有向(无向)加权图

邻接表的一般构造 #include<bits/stdc.h> #define N 1e4 using namespace std; typedef struct BP{ int P;//边所指的顶点位置 struct BP *nextB;//指向下一条边的指针 int Q;//储存边的信息 }BP; typedef struct DP{ int date;//顶点信息 BP *FirstB;//指向第一条连接…

RabbitMQ交换机类型

RabbitMQ交换机类型 1、RabbitMQ工作模型2、RabbitMQ交换机类型2.1、Fanout Exchange&#xff08;扇形&#xff09;2.1.1、介绍2.1.2、示例2.1.2.1、生产者2.1.2.2、消费者2.1.2.3、测试 2.2、Direct Exchange&#xff08;直连&#xff09;2.2.1、介绍2.2.2、示例2.2.2.1、生产…

字符串算法

字符串 1.kmp匹配算法Anya and 1100 1.kmp匹配算法 模板题链接 不懂可以看这个~详细的思路 #include <string> #include <iostream>using namespace std; const int N 1000010;string s,p;// s[]是长文本&#xff0c;p[]是模式串&#xff0c;n是s的长度&#xff…

WSL开发--利用Git连接远程仓库(详细步骤)

这篇文章主要介绍了如何将本地项目推送到 GitLab 上&#xff0c;并且避免每次提交都需要输入用户名和密码。文中分步讲解了配置 GitLab SSH 密钥以及配置 Git 远程仓库地址的方法。以下是文章的优化和简洁版&#xff1a; 将本地项目推送到 GitLab 并配置 SSH 免密登录 为了方便…

操作系统(10) (并发(2)------基于软件/硬件/操作系统层面解决两个进程之间的临界区问题/抢占式/非抢占式内核)

目录 1. 基于软件层面(Petersons Solution) Petersons Solution 满足三个要求: 好处: 缺点 2. 基于硬件层面 1. Disabling Interrupts (禁用中断) 概念解释&#xff1a; 代码框架&#xff1a; 要求&#xff1a; 禁用中断的好处与问题&#xff1a; 2. Test and Set Lock (…

基于 JAVASSM 框架沙县小吃点餐系统

基于 JAVASSM 框架&#xff08;即 Java Spring Spring MVC MyBatis&#xff09;开发一个沙县小吃点餐系统。 步骤一&#xff1a;需求分析 明确系统需要实现的功能&#xff0c;比如&#xff1a; 用户注册和登录浏览菜单添加菜品到购物车下单并支付订单管理后台管理&#…

零基础Java第十三期:继承与多态(一)

目录 一、继承 1.1. 继承的目的 1.2. 继承的概念 1.3. 继承的语法 1.4. 父类的访问 1.5. 继承中的重载与重写 1.6. 子类的构造方法 1.7. 再谈初始化 一、继承 1.1. 继承的目的 我们来定义一个Dog和Cat的类&#xff1a; public class Dog {public int age;public Strin…

论文翻译 | Evaluating the Robustness of Discrete Prompts

摘要 离散提示已被用于调整预训练语言模型&#xff0c;以适应不同的NLP任务。特别是&#xff0c;从一小组训练实例中生成离散提示的自动方法已经报告了优越的性能。然而&#xff0c;仔细观察习得的提示会发现&#xff0c;它们包含嘈杂和反直觉的词汇结构&#xff0c;而这些在手…

SQL,力扣题目1549,每件商品的最新订单【窗口函数】

一、力扣链接 LeetCode_1549 二、题目描述 表: Customers ------------------------ | Column Name | Type | ------------------------ | customer_id | int | | name | varchar | ------------------------ customer_id 是该表主键. 该表包含消费者的…

mysql查表相关练习

作业要求&#xff1a; 单表练习&#xff1a; 1 . 查询出部门编号为 D2019060011 的所有员工 2 . 所有财务总监的姓名、编号和部门编号。 3 . 找出奖金高于工资的员工。 4 . 找出奖金高于工资 40% 的员工。 5 找出部门编号为 D2019090011 中所有财务总监&#xff0c;和…

广东网站设计提升你网站在搜索引擎中的排名

在当今网络盛行的时代&#xff0c;拥有一个设计优良的网站&#xff0c;对企业的在线发展至关重要。特别是对于广东地区的企业来说&#xff0c;网站设计不仅仅是美观的问题&#xff0c;更直接影响着搜索引擎中的排名。因此&#xff0c;精心策划和设计的网站&#xff0c;能够显著…

qt QGroupBox详解

1、概述 QGroupBox是Qt框架中的一个容器控件&#xff0c;主要用于组织和管理一组相关的控件&#xff08;如按钮、复选框、文本框等&#xff09;&#xff0c;并为这些控件提供一个框架和标题。通过使用QGroupBox&#xff0c;可以创建具有逻辑分组和视觉层次结构的用户界面&…

数据库管理-第256期 Oracle DB 23.6新特性一览(20241031)

数据库管理256期 2024-10-31 数据库管理-第256期 Oracle DB 23.6新特性一览&#xff08;20241031&#xff09;1 AI向量搜索&#xff1a;新的向量距离度量2 混合向量索引3 分区&#xff1a;本地邻近分区向量索引4 持久邻近图向量索引5 稀疏向量6 邻居图向量索引的事务支持7 特征…

应急响应----本地环境配置,对内存马的研究分析

应急响应----本地环境配置,对内存马查杀研究分析 注:后续添加的补充内容框架型内存马 SpringController型内存马:动态注册Controller及映射路由。 SpringInterceptor型内存马:动态注册Interceptor及映射路由。 启动环境: Spring框架启动(Controller型内存马和Intercept…