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

二分查找题目:有序数组中的单一元素

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:有序数组中的单一元素

出处:540. 有序数组中的单一元素

难度

4 级

题目描述

要求

给定一个仅由整数组成的升序数组,其中每个元素都出现两次,除了一个元素只出现一次。

返回只出现一次的元素。

要求时间复杂度是 O(log n) \texttt{O(log n)} O(log n),空间复杂度是 O(1) \texttt{O(1)} O(1)

示例

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8] \texttt{nums = [1,1,2,3,3,4,4,8,8]} nums = [1,1,2,3,3,4,4,8,8]
输出: 2 \texttt{2} 2

示例 2:

输入: nums = [3,3,7,7,10,11,11] \texttt{nums = [3,3,7,7,10,11,11]} nums = [3,3,7,7,10,11,11]
输出: 10 \texttt{10} 10

数据范围

  • 1 ≤ nums.length ≤ 10 5 \texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{5} 1nums.length105
  • 0 ≤ nums[i] ≤ 10 5 \texttt{0} \le \texttt{nums[i]} \le \texttt{10}^\texttt{5} 0nums[i]105

解法一

思路和算法

由于给定的数组已经排序,因此相同元素在数组中一定位于相邻的位置。对于只出现一次的元素,该元素的左边和右边各有偶数个元素。假设只出现一次的元素位于下标 index \textit{index} index,考虑下标 x x x 处的元素, x ≠ index x \ne \textit{index} x=index

  • x < index x < \textit{index} x<index 时,只出现一次的元素在下标 x x x 的右边。如果 x x x 是偶数,则 nums [ x ] = nums [ x + 1 ] \textit{nums}[x] = \textit{nums}[x + 1] nums[x]=nums[x+1];如果 x x x 是奇数,则 nums [ x ] = nums [ x − 1 ] \textit{nums}[x] = \textit{nums}[x - 1] nums[x]=nums[x1]

  • x > index x > \textit{index} x>index 时,只出现一次的元素在下标 x x x 的左边。如果 x x x 是偶数,则 nums [ x ] = nums [ x − 1 ] \textit{nums}[x] = \textit{nums}[x - 1] nums[x]=nums[x1];如果 x x x 是奇数,则 nums [ x ] = nums [ x + 1 ] \textit{nums}[x] = \textit{nums}[x + 1] nums[x]=nums[x+1]

对于下标 x x x,可以根据 x x x 的奇偶性以及与 nums [ x ] \textit{nums}[x] nums[x] 相同的元素下标判断只出现一次的元素位于下标 x x x 处、下标 x x x 的左边或下标 x x x 的右边。因此可以使用二分查找得到只出现一次的元素的下标。

low \textit{low} low high \textit{high} high 分别表示二分查找的下标范围的下界和上界,初始时 low \textit{low} low high \textit{high} high 分别为数组的最小下标和最大下标。每次查找时,取 mid \textit{mid} mid low \textit{low} low high \textit{high} high 的平均数向下取整,执行如下操作。

  • 如果 mid \textit{mid} mid 是偶数且 nums [ mid ] = nums [ mid + 1 ] \textit{nums}[\textit{mid}] = \textit{nums}[\textit{mid} + 1] nums[mid]=nums[mid+1],或 mid \textit{mid} mid 是奇数且 nums [ mid ] = nums [ mid − 1 ] \textit{nums}[\textit{mid}] = \textit{nums}[\textit{mid} - 1] nums[mid]=nums[mid1],则只出现一次的元素位于下标 mid \textit{mid} mid 的右边,因此在下标范围 [ mid + 1 , high ] [\textit{mid} + 1, \textit{high}] [mid+1,high] 中继续查找。

  • 否则,只出现一次的元素位于下标 mid \textit{mid} mid 或其左边,因此在下标范围 [ low , mid ] [\textit{low}, \textit{mid}] [low,mid] 中继续查找。

low = high \textit{low} = \textit{high} low=high 时,查找结束,此时 low \textit{low} low 即为只出现一次的元素的下标, nums [ low ] \textit{nums}[\textit{low}] nums[low] 即为只出现一次的元素。

代码

class Solution {public int singleNonDuplicate(int[] nums) {int low = 0, high = nums.length - 1;while (low < high) {int mid = low + (high - low) / 2;if (mid % 2 == 0 && nums[mid] == nums[mid + 1] || mid % 2 == 1 && nums[mid] == nums[mid - 1]) {low = mid + 1;} else {high = mid;}}return nums[low];}
}

复杂度分析

  • 时间复杂度: O ( log ⁡ n ) O(\log n) O(logn),其中 n n n 是数组 nums \textit{nums} nums 的长度。二分查找的范围是数组的全部 n n n 个下标,二分查找的时间复杂度是 O ( log ⁡ n ) O(\log n) O(logn)

  • 空间复杂度: O ( 1 ) O(1) O(1)

解法二

思路和算法

由于只出现一次的元素的左边有偶数个元素,因此只出现一次的元素一定位于偶数下标,可以只在偶数下标中二分查找。

由于给定的数组长度是奇数,因此数组的最小下标和最大下标都是偶数,二分查找的下标范围的下界和上界的初始值分别为数组的最小下标和最大下标。每次查找时,取 mid \textit{mid} mid low \textit{low} low high \textit{high} high 的平均数向下取整,如果得到的 mid \textit{mid} mid 是奇数则将 mid \textit{mid} mid 1 1 1,确保 mid \textit{mid} mid 是偶数,执行如下操作。

  • 如果 nums [ mid ] = nums [ mid + 1 ] \textit{nums}[\textit{mid}] = \textit{nums}[\textit{mid} + 1] nums[mid]=nums[mid+1],则只出现一次的元素位于下标 mid \textit{mid} mid 的右边,因此在下标范围 [ mid + 2 , high ] [\textit{mid} + 2, \textit{high}] [mid+2,high] 中继续查找。

  • 否则,只出现一次的元素位于下标 mid \textit{mid} mid 或其左边,因此在下标范围 [ low , mid ] [\textit{low}, \textit{mid}] [low,mid] 中继续查找。

二分查找过程中,每次更新后的下标范围的下界和上界都是偶数,确保只在偶数下标中二分查找。

low = high \textit{low} = \textit{high} low=high 时,查找结束,此时 low \textit{low} low 即为只出现一次的元素的下标, nums [ low ] \textit{nums}[\textit{low}] nums[low] 即为只出现一次的元素。

代码

class Solution {public int singleNonDuplicate(int[] nums) {int low = 0, high = nums.length - 1;while (low < high) {int mid = low + (high - low) / 2;if (mid % 2 != 0) {mid--;}if (nums[mid] == nums[mid + 1]) {low = mid + 2;} else {high = mid;}}return nums[low];}
}

复杂度分析

  • 时间复杂度: O ( log ⁡ n ) O(\log n) O(logn),其中 n n n 是数组 nums \textit{nums} nums 的长度。二分查找的范围是数组的 n + 1 2 \dfrac{n + 1}{2} 2n+1 个偶数下标,二分查找的时间复杂度是 O ( log ⁡ n ) O(\log n) O(logn)

  • 空间复杂度: O ( 1 ) O(1) O(1)

相关文章:

二分查找题目:有序数组中的单一元素

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;有序数组中的单一元素 出处&#xff1a;540. 有序数组中的单一元素 难度 4 级 题目描述 要求 给定一个仅由整数…...

springboot基于Android的华蓥山旅游导航系统

摘 要 华蓥山旅游导航系统是一款专为华蓥山景区设计的智能导览应用&#xff0c;旨在为用户提供便捷的旅游信息服务。该系统通过整合华蓥山的地理信息、景点介绍、交通状况等数据&#xff0c;实现了对景区的全面覆盖。用户可以通过该系统获取实时的旅游资讯、交流论坛、地图等。…...

面向对象编程(OOP)深度解析:思想、原则与应用

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;Java &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 面向对象编程&#xff08;OOP&#xff09;深度解析&#xff1a;思想、原则与应用 一、面向对象编程的基本…...

iPhone 17 Air看点汇总:薄至6mm 刷新苹果轻薄纪录

我们姑且将这款iPhone 17序列的超薄SKU称为“iPhone 17 Air”&#xff0c;Jeff Pu在报告中提到&#xff0c;我同意最近关于 iPhone 17超薄机型采用6 毫米厚度超薄设计的传言。 如果这一测量结果被证明是准确的&#xff0c;那么将有几个值得注意的方面。 首先&#xff0c;iPhone…...

「OpenCV交叉编译」ubuntu to arm64

Ubuntu x86_64 交叉编译OpenCV 为 arm64OpenCV4.5.5、cmake version 3.16.3交叉编译器 gcc-arm-10.2-2020.11-x86_64-aarch64-none-linux-gnu 可在arm或linaro官网下载所需版本&#xff0c;本文的交叉编译器可点击链接跳转下载 Downloads | GNU-A Downloads – Arm Developer L…...

Stable Diffusion的解读(二)

Stable Diffusion的解读&#xff08;二&#xff09; 文章目录 Stable Diffusion的解读&#xff08;二&#xff09;摘要Abstract一、机器学习部分1. 算法梳理1.1 LDM采样算法1.2 U-Net结构组成 2. Stable Diffusion 官方 GitHub 仓库2.1 安装2.2 主函数2.3 DDIM采样器2.4 Unet 3…...

amd显卡和nVidia显卡哪个好 amd和英伟达的区别介绍

AMD和英伟达是目前市场上最主要的两大显卡品牌&#xff0c;它们各有自己的特点和优势&#xff0c;也有不同的适用场景和用户群体。那么&#xff0c;AMD显卡和英伟达显卡到底哪个好&#xff1f;它们之间有什么区别&#xff1f;我们又该如何选择呢&#xff1f;本文将从以下几个方…...

软件测试—— Selenium 常用函数(一)

前一篇文章&#xff1a;软件测试 —— 自动化基础-CSDN博客 目录 前言 一、窗口 1.屏幕截图 2.切换窗口 3.窗口设置大小 4.关闭窗口 二、等待 1.等待意义 2.强制等待 3.隐式等待 4.显式等待 总结 前言 在前一篇文章中&#xff0c;我们介绍了自动化的一些基础知识&a…...

为什么verilog中递归函数需要定义为automatic?

直接上代码 module automatic_tb;reg [7:0] value;initial begin #0 value < 8d5;#10 $display("result of automatic: %0d", factor_automatic(value));$display("result of static: %0d", factor_static(value));#50 $stop; endfunction reg[7:0] fa…...

23种设计模式-状态(State)设计模式

文章目录 一.什么是状态模式&#xff1f;二.状态模式的结构三.状态模式的应用场景四.状态模式的优缺点五.状态模式的C实现六.状态模式的JAVA实现七.代码解释八.总结 类图&#xff1a; 状态设计模式类图 一.什么是状态模式&#xff1f; 状态模式&#xff08;State Pattern&…...

EventListener与EventBus

EventListener JDK JDK1.1开始就提供EventListener&#xff0c;一个标记接口&#xff0c;源码如下&#xff1a; /*** A tagging interface that all event listener interfaces must extend.*/ public interface EventListener { }JDK提供的java.util.EventObject&#xff1…...

Facebook为什么注册失败了?该怎么解决?

有时候用户在尝试注册Facebook账号时可能会遇到各种问题&#xff0c;导致注册失败或遇到困难。小编会为大家分析Facebook注册失败的可能原因&#xff0c;并提供解决方法&#xff0c;帮助大家顺利完成注册流程。 一、Facebook注册失败的可能原因 1. 账号信息问题&#xff1a; …...

前端数据可视化思路及实现案例

目录 一、前端数据可视化思路 &#xff08;一&#xff09;明确数据与目标 &#xff08;二&#xff09;选择合适的可视化图表类型 &#xff08;三&#xff09;数据与图表的绑定及交互设计 &#xff08;四&#xff09;页面布局与样式设计 二、具体案例&#xff1a;使用 Ech…...

【DVWA】Brute Force暴力破解实战

问尔辈 何等样人 自摸心头 再来求我&#xff1b;若汝能 克存忠孝 持身正直 不拜何妨 1.Brute Force(Low) 相关的代码分析 if( isset( $_GET[ Login ] ) ) {// Get username$user $_GET[ username ];// Check the database$query "SELECT * FROM users WHERE user $…...

23种设计模式速记法

前言 在软件开发的过程中&#xff0c;设计模式作为解决常见问题的通用模板&#xff0c;一直是开发者的重要工具。尤其是在面临复杂系统架构和需求变化时&#xff0c;设计模式不仅能够提升代码的可复用性和扩展性&#xff0c;还能大大提高团队之间的协作效率。然而&#xff0c;…...

第7章硬件测试-7.3 功能测试

7.3 功能测试 7.3.1 整机规格测试7.3.2 整机试装测试7.3.3 DFX测试 功能测试包括整机规格、整机试装和整机功能测试&#xff0c;是整机结构和业务相关的测试。 7.3.1 整机规格测试 整机规格测试包括尺寸、重量、温度、功耗等数据。这些测试数据与设计规格进行比对和校验&…...

动态规划子数组系列一>等差数列划分

题目&#xff1a; 解析&#xff1a; 代码&#xff1a; public int numberOfArithmeticSlices(int[] nums) {int n nums.length;int[] dp new int[n];int ret 0;for(int i 2; i < n; i){dp[i] nums[i] - nums[i-1] nums[i-1] - nums[i-2] ? dp[i-1]1 : 0;ret dp[i…...

《Python浪漫的烟花表白特效》

一、背景介绍 烟花象征着浪漫与激情&#xff0c;将它与表白结合在一起&#xff0c;会创造出别具一格的惊喜效果。使用Python的turtle模块&#xff0c;我们可以轻松绘制出动态的烟花特效&#xff0c;再配合文字表白&#xff0c;打造一段专属的浪漫体验。 接下来&#xff0c;让…...

什么是RESTful API,有什么特点

RESTful API 概述 什么是 RESTful API&#xff1f; RESTful API 是基于 Representational State Transfer&#xff08;表现层状态转移&#xff09;架构风格的 Web 服务接口。REST 是一种设计风格&#xff0c;而不是具体的协议或标准。它定义了一组约束和最佳实践&#xff0c;…...

友思特新闻 | 友思特荣获广州科技创新创业大赛智能装备行业赛初创组优胜企业!

2024年11月19日&#xff0c;第十三届中国创新创业大赛&#xff08;广东广州赛区&#xff09;暨2024年广州科技创新创业大赛智能装备行业赛颁奖典礼隆重举行。 赛事奖项介绍&#xff1a;广州科技创新创业大赛智能装备行业赛 第十三届“中国创新创业大赛&#xff08;广东广州赛区…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...