【LeetCode】每日一题 2024_11_10 有序数组中的单一元素(二分)

embedded/2024/11/13 22:33:40/

前言

每天和你一起刷 LeetCode 每日一题~

LeetCode 启动!

题目:leetcode.cn/problems/single-element-in-a-sorted-array/description/?envType=daily-question&envId=2024-11-10" rel="nofollow">有序数组中的单一元素

代码与解题思路

先读题:

“一个仅由整数组成的有序数组”

“你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。”

看到这里基本上就能看出来题目要求我们用二分来做这道题目了,这题也是一道经典题目,在题目没给有序以及复杂度要求的时候,直接模拟,用哈希,或者用异或都可以很轻松的解答

怎么用二分做这道题呢?

核心思路:

“有一个数只会出现一次”

我们可以看到,示例一:[1,1,2,3,3,4,4,8,8]

在只出现一次的数字出现之前,偶数下标和下一个奇数下标的元素是相同的,而在特殊数字出现之后,偶数下标和下一个奇数下标的元素就不相同的了

很显然,该数组具有单调性,元素相同证明特殊数字在左区间,元素不相同证明特殊数字在右区间

最后一个问题,怎么样做到每次二分的是偶数下标?让二分上界 / 2,在取到 mid 之后让 mid * 2 这样得到就一定是偶数的下标了~

代码如下:

func singleNonDuplicate(nums []int) int {l, r := 0, len(nums)/2for l < r {mid := (l+r)/2if nums[mid*2] != nums[mid*2+1] {r = mid} else {l = mid + 1}}return nums[l*2]
}

每天进步一点点,我们明天不见不散~

可以和我刷一辈子的每日一题吗?
一题一题,积累起来就是一辈子。


http://www.ppmy.cn/embedded/136858.html

相关文章

论文翻译 | Chain of Hindsight aligns LanguageModels with Feedback

摘要 从人类偏好中学习对于语言模型匹配人类需求并与人类和社会价值观保持一致非常重要。先前的研究通过学习人类的反馈来理解和遵循指令&#xff0c;取得了显著的成功。尽管如此&#xff0c;这些方法要么是建立在人工注释者青睐的精心挑选的模型上&#xff0c;这使得它们在数据…

PySimpleGUI 库 和 pymsql 库

PySimpleGUI 库 PySimpleGUI 是一个用于简化 GUI 编程的 Python 包&#xff0c;它封装了多种底层 GUI 框架&#xff08;如 tkinter、Qt、WxPython 等&#xff09;&#xff0c;提供了简单易用的 API。PySimpleGUI 包含了大量的控件&#xff08;也称为小部件或组件&#xff09;&…

AI笔筒操作说明及应用场景

AI笔筒由来&#xff1a; 在快节奏的现代办公环境中&#xff0c;我们一直在寻找既能提升效率、增添便利&#xff0c;又能融入企业文化、展现个人品味的桌面伙伴。为此&#xff0c;我们特推出专为追求卓越、注重细节的您设计的AI笔筒礼品版&#xff0c;它集高科技与实用性于一身…

在 Jupyter Notebook 中使用 Matplotlib 进行交互式可视化的教程

在 Jupyter Notebook 中使用 Matplotlib 进行交互式可视化的教程 引言 数据可视化是数据分析的重要组成部分&#xff0c;能够帮助我们更直观地理解数据。Matplotlib 是 Python 中最流行的绘图库之一&#xff0c;而 Jupyter Notebook 则是进行数据分析和可视化的理想环境。本文…

jupyter+pycharm内部直接运行

第一步&#xff1a;终端使用conda&#xff0c;切换到目标环境&#xff0c;在该虚拟环境下 下载jupyter支持包&#xff08;pip install jupyter&#xff09; 第二步&#xff1a;解决root用户不能直接运行的问题 创建配置文件 jupyter notebook --generate-config 修改…

Linux【基础篇】

-- 原生罪 linux的入门安装学习 什么是操作系统&#xff1f; 用户通过操作系统和计算机硬件联系使用。桥梁~ 什么是Linux&#xff1f; 他是一套开放源代码&#xff08;在互联网上找到Linux系统的源代码&#xff0c;C语言写出的软件&#xff09;&#xff0c;可以自由 传播&…

推荐一款功能强大的视频修复软件:Apeaksoft Video Fixer

Apeaksoft Video Fixer是一款功能强大的视频修复软件&#xff0c;专门用于修复损坏、不可播放、卡顿、画面失真、黑屏等视频问题。只需提供一个准确且有效的样本视频作为参考&#xff0c;该软件就能将受损视频修复到与样本视频相同的质量。该软件目前支持MP4、MOV、3GP等格式的…

在Scrapy爬虫中应用Crawlera进行反爬虫策略

在互联网时代&#xff0c;数据成为了企业竞争的关键资源。然而&#xff0c;许多网站为了保护自身数据&#xff0c;会采取各种反爬虫技术来阻止爬虫的访问。Scrapy作为一个强大的爬虫框架&#xff0c;虽然能够高效地抓取网页数据&#xff0c;但在面对复杂的反爬虫机制时&#xf…