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来实现对指定窗口的键盘操作。以下是一些关键的…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
PydanticAI快速入门示例
参考链接:https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...
