Leetcode:540. 有序数组中的单一元素
题目
给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
输入: nums = [3,3,7,7,10,11,11]
输出: 10
思路
题目说每个元素都会出现两次,唯有一个数只会出现一次而且是有序的,那说明如果单个元素下标为i,i 左边要匹配的元素在左边,同理右边也一样。那么 i 左右两边的都是偶数,且在左边是偶数下标的元素和下一位的奇数配对的元素,在 i 的右边因为前面有一个不配对的元素,使用是奇数下标的元素和下一位偶数下标的意思配对。题目要求O(log n),那可以使用二分查找。以偶数和下一位奇数配对的为准寻找。
代码
class Solution {
public:int singleNonDuplicate(vector<int>& nums) {int low = 0, high = nums.size() - 1;while (low < high) {int mid = (high - low) / 2 + low;mid -= mid & 1;//为了确保 mid 是偶数索引if (nums[mid] == nums[mid + 1]) {low = mid + 2;} else {high = mid;}}return nums[low];}
};
总结
- 二分查找可以以数组其中变化的为准找
- mid 是偶数索引 mid -= mid & 1
相关文章:
Leetcode:540. 有序数组中的单一元素
题目 给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。 请你找出并返回只出现一次的那个数。 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。 输入: nums [1,1,2,3,3,4,4,8,8] 输出: 2 输入:…...
Python数据分析NumPy和pandas(二十七、数据可视化 matplotlib API 入门)
数据可视化或者数据绘图是数据分析中最重要的任务之一,是数据探索过程的一部分,数据可视化可以帮助我们识别异常值、识别出需要的数据转换以及为模型生成提供思考依据。对于Web开发人员,构建基于Web的数据可视化显示也是一种重要的方式。Pyth…...
数组指针和指针的区别
区分数组指针和指针数组 int *p[3]和 int (*p)[3] 根据运算符的优先级,"[]"的优先级是高于“*”的,p就会先与[]结合,那么它本质就是数组,数组内存放的是指针,它叫指针数组。(int*p[3]ÿ…...
Linux git-bash配置
参考资料 命令提示符Windows下的Git Bash配置,提升你的终端操作体验WindowsTerminal添加git-bash 目录 一. git-bash配置1.1 解决中文乱码1.2 修改命令提示符 二. WindowsTerminal配置git-bash2.1 添加git-bash到WindowsTerminal2.2 解决删除时窗口闪烁问题 三. VS…...
【后端速成Vue】computed计算属性
前言: 本期将会介绍 Vue 中的计算属性,他和 methods 方法又会有什么区别呢?在这里都会给你一一讲解。 篮球哥找工作专属IT岗位内部推荐: 专属内推链接:内推通道 1、computed计算属性 概念: 基于现有的数据…...
力扣-每日温度
. - 力扣(LeetCode) 这是我的第一个思路 虽然可以得到正确答案 但是过于暴力 已经超出了时间限制 class Solution { public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int>ans;for (int i 0; i <…...
(Go语言)初上手Go?本篇文章帮拿捏Go的数据类型!
1. bool 类型 布尔类型:只有 true 和 false 两种值 在Go中,整数 0 不代表 false 值,1也不代表 true 值 即数字无法代替布尔值进行逻辑判断,两者是完全不同的类型 布尔类型占用 1 字节 2. int 整型 Go中为不同位数的整数分配…...
支付宝域名如何加入白名单(扫码老是弹窗)
支付宝扫码之后,遇到非支付宝官方网页,请确认是否继续访问弹窗,问题解决办法。 本章教程提供解决办法,亲测有效。 一、打开支付宝开放平台 登录地址:https://open.alipay.com/ 然后进行扫码登录。 1、打开网页/移动应用开发 2、前往创建 3、创建应用...
嵌入式学习第21天Linux基础
目录 第1章 Linux 系统介绍 1.1 Unix 操作系统(了解) 1.2 Linux 操作系统(了解) 1.3 Linux 操作系统的主要特性(重点) 1.4 Linux 与 Unix 的区别与联系 1.5 GUN 与 GPL(了解) …...
【activiti工作流源码集成】springboot+activiti+mysql+vue+redis工作流审批流集成整合业务绑定表单流程图会签驳回
工作流集成实际项目案例,demo提供 源码获取方式:本文末个人名片直接获取。 前言 activiti工作流引擎项目,企业erp、oa、hr、crm等企事业办公系统轻松落地,请假审批demo从流程绘制到审批结束实例。 一、项目形式 springbootvue…...
华为私有接口类型hybrid
华为私有接口类型hybrid Tip:hybrid类型,简称混合型接口。 本次实验模拟2层网络下 vlan10 vlan20 不能互访,vlan10 vlan20 同时可以访问vlan100 sw1配置如下: <Huawei>sy [Huawei]sys sw1 [sw1]vl ba 10 20 100 [sw1]int…...
计算机的错误计算(一百五十)
摘要 探讨 MATLAB 中 的计算精度问题。当 为含有小数的大数或 ()附近数时,输出会有错误数字。 例1. 已知 计算 直接贴图吧: 另外,16位的正确值分别为 -0.7882256119904400e0、0.1702266977524110e0、-0.…...
【模块化大作战】Webpack如何搞定CommonJS与ES6混战(3)
在前端开发中,模块化是一个重要的概念,不同的模块化标准有不同的特点和适用场景。webpack 同时支持 CommonJS 和 ES6 Module,因此需要理解它们在互操作时 webpack 是如何处理的。 同模块化标准 如果导出和导入使用的是同一种模块化标准&…...
工程认证与Spring Boot:计算机课程管理的新探索
摘要 随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了基于工程教育认证的计算机课程管理平台的开发全过程。通过分析基于工程教育认证的计算机课程管理平台管理的不足,创建了一个计算机管理基于工程教育认…...
vue3的自定义hooks怎么写?
写个hook函数去追踪鼠标位置: 没用hook前: <script setup> import { ref, onMounted, onUnmounted } from vueconst x ref(0) const y ref(0)function update(event) {x.value event.pageXy.value event.pageY }onMounted(() > window.ad…...
SpringBoot项目编译报错 类文件具有错误的版本 61.0, 应为 52.0
springboot项目在编译时报错: /Users/Apple/Developer/art/caicai/cai-api/dubbo-samples/1-basic/dubbo-samples-spring-boot/dubbo-samples-spring-boot-provider/src/main/java/org/apache/dubbo/springboot/demo/provider/ProviderApplication.java:22:32 java…...
【网络】应用层——HTTP协议
> 作者:დ旧言~ > 座右铭:松树千年终是朽,槿花一日自为荣。 > 目标:了解什么是HTTP协议。 > 毒鸡汤:有些事情,总是不明白,所以我不会坚持。早安! > 专栏选自:网络 &g…...
ServletContext介绍
文章目录 1、ServletContext对象介绍1_方法介绍2_用例分析 2、ServletContainerInitializer1_整体结构2_工作原理3_使用案例 3、Spring案例源码分析1_注册DispatcherServlet2_注册配置类3_SpringServletContainerInitializer 4_总结 ServletContext 表示上下文对象,…...
让AI帮我用java实现EasyExel读取图片—支持WPS嵌入图片
🌈 场景概述 java 小伙伴相信都使用 EasyExcel 以及 POI 库实现过 Excel 批量导入、导出功能,但只有部分人实现过 excel 导入带图片数据的场景。这个技术实现手段网上也有很多案例和demo,最常见的就是通过 XSSFPictureData 来实现。但是在 W…...
C# 实现对指定句柄的窗口进行键盘输入的实现
在C#中实现对指定句柄的窗口进行键盘操作,可以通过多种方式来实现。以下是一篇详细的指南,介绍如何在C#中实现这一功能。 1. 使用Windows API函数 在C#中,我们可以通过P/Invoke调用Windows API来实现对指定窗口的键盘操作。以下是一些关键的…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
全面解析数据库:从基础概念到前沿应用
在数字化时代,数据已成为企业和社会发展的核心资产,而数据库作为存储、管理和处理数据的关键工具,在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理,到社交网络的用户数据存储,再到金融行业的交易记录处理&a…...
