leetcode 540. Single Element in a Sorted Array(排序数组中的单个元素)

给一个已经排好序的升序数组,其中每个元素都会重复2次,只有一个元素只有一个,
找出这个只有一个的元素。
要求时间复杂度在O(logn), 空间复杂度在O(1).
思路:
时间复杂度为O(logn), 让人想到了binary search.
因为时间复杂度为O(1), 所以不能用一个数组来保存每个元素出现的次数。
不过,每个元素也就出现2次,而且是排好序的,也就是说相同的元素都是在一起的。
可以用一个cnt, 元素第一次出现时cnt = 1, 第2次出现时cnt = 0,
那么只出现一次的元素,cnt就无法清0,于是就被找出来了。
但是这种方法需要遍历数组,时间复杂度为O(n), 也能通过测试。
public int singleNonDuplicate(int[] nums) {int cnt = 1;int n = nums.length;if(n == 1) return nums[0];for(int i = 1; i < n; i++) {if(nums[i] != nums[i-1]) {if(cnt == 1) return nums[i-1];else cnt = 1;} else {cnt = 0;}}return nums[n-1];}
下面看一下binary search.
为什么能用binary search呢?
因为每个元素出现2次(长度为偶数),只有一个元素出现了1次,
包含出现了1次的元素的部分,长度一定是奇数。
我们可以判断奇数的长度出现在左边还是右边,把left, right指针卡在奇数长度的部分。
举个例子:
2,2,3,3,4
[0] [1] [2] [3] [4]
left = 0, right = 4, mid = 2
右半边的长度(不含mid本身)为right - mid = 2, 长度为偶数,
但是发现没有,nums[mid]和nums[mid+1]两个数是一样的,
现在的长度right-mid 把两个相同的元素拆开了,违背了刚才判断的标准,
2个相同的元素都在一起才符合长度为偶数的标准,拆开了就不能按照长度为奇偶来判断了。
所以要比较nums[mid]和nums[mid+1]两个元素,如果相同,把nums[mid]也算进右边,
所以现在右边长度为奇数,可以判断单个的元素在右边,移动left = mid + 2(跳过重复元素)。
那如果是下面的例子:
1,2,2,3,3,
可以看到右边长度为偶数,这时要移动right = mid - 2(跳过重复元素)
直到nums[mid] 和 nums[mid + 1], nums[mid-1]都不相等, 返回nums[mid].
public int singleNonDuplicate(int[] nums) {int n = nums.length;if(n == 1) return nums[0];int left = 0;int right = n - 1;while(left <= right) {int mid = left + (right - left)/2;boolean isEvenLen = ((right - mid) % 2 == 0);if(mid >= 1 && nums[mid] == nums[mid-1]) {if(isEvenLen) right = mid-2;else left = mid + 1;//重复元素算进右边长度} else if(mid < n - 1 && nums[mid] == nums[mid+1]) {if(isEvenLen) left = mid + 2; //算进重复元素后,右边长度为奇数,单个元素在右边else right = mid - 1;} else {return nums[mid];}}return -1;}
相关文章:
leetcode 540. Single Element in a Sorted Array(排序数组中的单个元素)
给一个已经排好序的升序数组,其中每个元素都会重复2次,只有一个元素只有一个, 找出这个只有一个的元素。 要求时间复杂度在O(logn), 空间复杂度在O(1). 思路: 时间复杂度为O(logn), 让人想到了binary search. 因为时间复杂度为…...
Color correction for tone mapping
Abstract色调映射算法提供了复杂的方法,将真实世界的亮度范围映射到输出介质的亮度范围,但它们经常导致颜色外观的变化。在本研究中,我们进行了一系列的主观外观匹配实验,以测量对比度压缩和增强后图像色彩的变化。结果表明&#…...
JavaScript-XHR-深入理解
JavaScript-XHR-深入理解1. XHR(Asynchronous JavaScript And XML)初始1.1. xhr request demo1.2. status of XHRHttpRequest1.3. send synchronous request by xhr1.4. onload监听数据加载完成1.5. http status code1.6. get/post request with josn/form/urlcoded1.7. encaps…...
mathtype7.0最新版安装下载及使用教程
MathType是一款专业的数学公式编辑器,理科生专用的必备工具,可应用于教育教学、科研机构、工程学、论文写作、期刊排版、编辑理科试卷等领域。2014年11月,Design Science将MathType升级到MathType 6.9版本。在苏州苏杰思网络有限公司与Design…...
响应状态码
✨作者:猫十二懿 ❤️🔥账号:CSDN 、掘金 、个人博客 、Github 🎉公众号:猫十二懿 一、状态码大类 状态码分类说明1xx响应中——临时状态码,表示请求已经接受,告诉客户端应该继续请求或者如果…...
第六章.卷积神经网络(CNN)—CNN的实现(搭建手写数字识别的CNN)
第六章.卷积神经网络(CNN) 6.2 CNN的实现(搭建手写数字识别的CNN) 1.网络构成 2.代码实现 import pickle import matplotlib.pyplot as plt import numpy as np import sys, ossys.path.append(os.pardir)from dataset.mnist import load_mnist from collections import Order…...
【go】defer底层原理
defer的作用 defer声明的函数在当前函数return之后执行,通常用来做资源、连接的关闭和缓存的清除等。 A defer statement pushes a function call onto a list. The list of saved calls is executed after the surrounding function returns. Defer is commonly u…...
TypeScript 学习笔记
最近在学 ts 顺便记录一下自己的学习进度,以及一些知识点的记录,可能不会太详细,主要是用来巩固和复习的,会持续更新 前言 想法 首先我自己想说一下自己在学ts之前,对ts的一个想法和印象,在我学习之前&a…...
【C++】map和set的使用
map和set一、set1.1 set的介绍1.2 set的使用1.2.1 set的构造1.2.2 set的迭代器1.2.3 set的修改1.2.3.1 insert && find && erase1.2.3.2 count1.3 multiset二、map2.1 map的介绍2.2 map的使用2.2.1 map的修改2.2.1.1 insert2.2.1.2 统计次数2.3 multimap一、se…...
微电影广告具有哪些特点?
微电影广告是广告主投资的,以微电影为形式载体,以新媒体为主要传播载体,综合运用影视创作手法拍摄的集故事性、艺术性和商业性于一体的广告。它凭借精彩的电影语言和强大的明星效应多渠道联动传播,润物细无声地渗透和传递着商品信…...
Android RxJava框架源码解析(四)
目录一、观察者Observer创建过程二、被观察者Observable创建过程三、subscribe订阅过程四、map操作符五、线程切换原理简单示例1: private Disposable mDisposable; Observable.create(new ObservableOnSubscribe<String>() {Overridepublic void subscribe(…...
Linux信号-进程退出状态码
当进程因收到信号被终止执行退出后,父进程可以通过wait或waitpid得到它的exit code。进程被各信号终止的退出状态码总结如下:信号编号信号名称信号描述默认处理方式Exit code1SIGHUP挂起终止12SIGINT终端中断终止23SIGQUIT终端退出终止、coredump1314SIG…...
springcloud+vue实现图书管理系统
一、前言: 今天我们来分享一下一个简单的图书管理系统 我们知道图书馆系统可以有两个系统,一个是管理员管理图书的系统,管理员可以(1)查找某一本图书情况、(2)增加新的图书、(3&…...
GEE学习笔记 六十:GEE中生成GIF动画
生成GIF动画这个是GEE新增加的功能之一,这一篇文章我会简单介绍一下如何使用GEE来制作GIF动画。 相关API如下: 参数含义: params:设置GIF动画显示参数,详细的参数可以参考ee.data.getMapId() callback:回调…...
react中的useEffect
是函数组件中执行的副作用,副作用就是指每次组件更新都会执行的函数,可以用来取代生命周期。 1. 基本用法 import { useEffect } from "react"; useEffect(()>{console.log(副作用); });2. 副作用分为需要清除的和不需要清除 假如设置…...
故障安全(Crash-Safe) 复制
二进制日志记录是故障安全的:MySQL 仅记录完成的事件或事务使用 sync-binlog 提高安全性默认值是1,最安全的,操作系统在每次事务后写入文件将svnc-binloq 设置为0,当操作系统根据其内部规则写入文件的同时服务器崩溃时性能最好但事务丢失的可…...
Spring aop之针对注解
前言 接触过Spring的都知道,aop是其中重要的特性之一。笔者在开发做项目中,aop更多地是要和注解搭配:在某些方法上加上自定义注解,然后要对这些方法进行增强(很少用execution指定,哪些包下的哪些方法要增强)。那这时就…...
【JavaScript速成之路】JavaScript数据类型转换
📃个人主页:「小杨」的csdn博客 🔥系列专栏:【JavaScript速成之路】 🐳希望大家多多支持🥰一起进步呀! 文章目录前言数据类型转换1,转换为字符串型1.1,利用“”拼接转换成…...
21-绑定自定义事件
绑定自定义事件 利用自定义事件获取子组件的值 父组件给子组件绑定一个自定义事件,实际上是绑定到了子组件的实例对象vc上: <!-- 自定义myEvent事件 --> <Student v-on:myEventgetStudentName/>在父组件中编写getStudentName的实现&#…...
【Mysql】触发器
【Mysql】触发器 文章目录【Mysql】触发器1. 触发器1.1 介绍1.2 语法1.2.1 创建触发器1.2.2 查看触发器1.2.3 删除触发器1.2.4 案例1. 触发器 1.1 介绍 触发器是与表有关的数据库对象,指在insert、update、delete之前(BEFORE)或之后(AFTER),触发并执行…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
C++--string的模拟实现
一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现,其目的是加强对string的底层了解,以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量,…...
CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx
“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网(IIoT)场景中,结合 DDS(Data Distribution Service) 和 Rx(Reactive Extensions) 技术,实现 …...
