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来实现对指定窗口的键盘操作。以下是一些关键的…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
uni-app学习笔记三十五--扩展组件的安装和使用
由于内置组件不能满足日常开发需要,uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件,需要安装才能使用。 一、安装扩展插件 安装方法: 1.访问uniapp官方文档组件部分:组件使用的入门教程 | uni-app官网 点击左侧…...
Python常用模块:time、os、shutil与flask初探
一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...
