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

剑指 Offer 53 - I. 在排序数组中查找数字 I

原题链接

难度:easy\color{Green}{easy}easy


题目描述

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

提示:

  • 0<=nums.length<=1050 <= nums.length <= 10^{5}0<=nums.length<=105
  • −109<=nums[i]<=109-10^{9} <= nums[i] <= 10^{9}109<=nums[i]<=109
  • numsnumsnums 是一个非递减数组
  • −109<=target<=109-10^{9} <= target <= 10^{9}109<=target<=109

注意:

  • 本题与主站 34 题相同(仅返回值不同):https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

  • 面试官出这题的话肯定是想让你写二分的啦 其他没用。

  • 给面试官说有两种类型的解法,一种是暴力,一种是二分法求边界,体现递进的思考过程,别上来一言不发写个二分,失去一个表现机会。

  • 对于二分法,我们可以分别求左边界和右边界,也可以二分求左边界之后接着遍历计数,两种情况对应在真实场景下连续相等的数据一般有多长。如果经常出现很长一串连续相等的数据,就用二分法求右边界,否则容易使算法退化到
    O(n)

  • 分析完了之后,给一个规范的解法,注意函数驼峰式命名这些能体现你专业性的小细节


算法1

(模拟)

创建一个变量 ans,扫描整个数组,如果数组中的值等于 target,那么 ans 就加一,最后输出答案。

复杂度分析

  • 时间复杂度O(n)O(n)O(n),其中 nnn 是数组的长度。需要遍历数组一次。

  • 空间复杂度 : O(1)O(1)O(1),只需要常数空间存放若干变量。

C++ 代码

class Solution {
public:int search(vector<int>& nums, int target) {int ans = 0;for (int i = 0; i < nums.size(); i ++) {if (nums[i] == target)ans ++;}return ans;}
};


算法2

(二分)

  • 排序数组 nums 中的所有数字 target 形成一个窗口,记窗口的 左 / 右边界 索引分别为 leftright ,分别对应窗口左边 / 右边的首个元素。

  • 本题要求统计数字 target 的出现次数,可转化为:使用二分法分别找到 左边界 left 和 右边界 right ,易得数字 target 的数量为 right−left−1

在这里插入图片描述

复杂度分析

  • 时间复杂度O(logn)O(logn)O(logn),二分法为对数级别复杂度。

  • 空间复杂度 : O(1)O(1)O(1),几个变量使用常数大小的额外空间。

C++ 代码

class Solution {
public:int search(vector<int>& nums, int target) {if (nums.size() == 0) return 0;int l = 0, r = nums.size() - 1;int ans = 0;//寻找最左边的下标while (l < r) {int mid = (l + r) / 2;if (nums[mid] >= target)r = mid;else l = mid + 1;}if (nums[l] != target) return ans;int left = l;l = 0, r = nums.size() - 1;//寻找右边的下标while (l < r) {int mid = (l + r + 1) / 2;if (nums[mid] <= target)l = mid;else r = mid - 1;}int right = l;ans = right - left + 1;return ans;}
};

相关文章:

剑指 Offer 53 - I. 在排序数组中查找数字 I

原题链接 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums [5,7,7,8,8,10], target 8 输出: 2示例 2: 输入: nums [5,7,7,8,8,10], target 6 输出: 0提示&#xff1a; 0<nums.length<1050 <…...

华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】

最近更新的博客 华为OD机试 - 热点网络统计 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 查找单入口空闲区域 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 好朋友 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 找出同班小朋友 | 备考思路,刷题要点…...

PowerShell Install Office 2021 Pro Plus Viso Professional

前言 微软Office在很长一段时间内都是最常用和最受欢迎的软件。从小型创业公司到大公司,它的使用比例相当。它可以很容易地从微软的官方网站下载。但是,微软只提供安装程序,而不提供完整的软件供下载。这些安装文件通常比较小。下载并运行后,安装的文件将从后端服务器安装M…...

KubeSphere实战

文章目录一、KubeSphere平台安装1、Kubernetes上安装KubeSphere1.1 安装docker1.2 安装Kubernetes1.3 前置环境之nfs存储1.4 前置环境之metrics-server1.5 安装KubeSphere2、Linux单节点部署KubeSphere3、Linux多节点部署KubeSphere(推荐)二、KubeSphere实战1、多租户实战2、中…...

Linux 简介

Linux 内核最初只是由芬兰人林纳斯托瓦兹&#xff08;Linus Torvalds&#xff09;在赫尔辛基大学上学时出于个人爱好而编写的。 Linux 是一套免费使用和自由传播的类 Unix 操作系统&#xff0c;是一个基于 POSIX 和 UNIX 的多用户、多任务、支持多线程和多 CPU 的操作系统。 …...

java面试题-泛型异常反射

泛型1.什么是泛型&#xff1f;Java是一种强类型语言&#xff0c;数据类型在编译时必须确定。如果我们想要在代码中使用不同类型的数据&#xff0c;那么就需要为每种类型分别写出相应的代码。这样会导致代码冗长、重复&#xff0c;也不便于维护。为了解决这个问题&#xff0c;Ja…...

详细解读ChatGPT:如何调用ChatGPT的API接口到官方例子的说明以及GitHub上的源码应用和csdn集成的ChatGPT

文章目录1. 解读ChatGPT1.1 词语解释1.2 功能解读2. GitHub上ChatGPT的应用源码3. 调用ChatGPT的API4. 官方例子说明5. 集成ChatGPT自ChatGPT出来到如今&#xff0c;始终走在火热的道路上&#xff0c;如今日活用户破亿&#xff0c;他为何有如此大的魅力&#xff0c;深受广大用户…...

九龙证券|最新评级情况出炉,机构扎堆这一板块!聚氨酯龙头获得最多关注

本周算计254家上市公司获组织“买入型”评级。 电子板块评级组织扎堆 证券时报数据宝计算&#xff0c;2月13日至17日&#xff0c;A股市场53家组织算计进行347次评级&#xff0c;254家上市公司获“买入型”评级&#xff08;包含买入、增持、强烈推荐、推荐&#xff09;。 从申…...

考研复试机试 | C++ | 尽量不要用python,很多学校不支持

目录1.1打印日期 &#xff08;清华大学上机题&#xff09;题目&#xff1a;代码&#xff1a;1.2改一改&#xff1a;上一题反过来问题代码&#xff1a;2.Day of Week &#xff08;上交&&清华机试题&#xff09;题目&#xff1a;代码&#xff1a;3.剩下的树&#xff08;清…...

ChatGPT时代,别再折腾孩子了

今天这篇完全是从两件事儿有感而发。昨天在文印店&#xff0c;在复印机上看到装订好的几页纸&#xff0c;我瞥了一眼&#xff0c;是历史知识点&#xff1a;隋朝大运河分为四段&#xff0c;分别是___ ___ ___ ___&#xff0c;连接了五大河___ ___ ___ ___ ______ 年&#xff…...

万字干货 | 荔枝魔方基于云原生的架构设计与实践

近年来&#xff0c;荔枝集团在国内和海外的业务迅速发展&#xff0c;业务数据规模也是成几何式地增长&#xff0c;海量数据的计算分析场景、业务智能算法应用需求随之而生&#xff0c;为了快速地满足业务发展的需要&#xff0c;我们面临着诸多的技术挑战。技术挑战工程问题资源…...

#科研筑基# python初学自用笔记 第九篇 面向对象编程

面向对象编程 Object Oriented Programming &#xff0c;简称OOP&#xff0c;是一种程序设计思想&#xff0c;这种思想把对象作为程序的基本单元。类是抽象的&#xff0c;对象是具体的&#xff0c;一种类包括其特定的数据或属性&#xff0c;以及操作数据的函数&#xff08;方法…...

Python快速上手系列--邮件发送--详解篇

本章就来一起学习一下跑完自动化脚本后如何自动的发送邮件到指定的邮箱。zmail操作&#xff1a;1. 导包 import zmail2. 邮件内容&#xff0c;包含&#xff1a;主题(subject)、正文(content_text)、附件(attachments)3. 发件人信息&#xff0c;包含&#xff1a;发件人账号&…...

【Bluetooth开发】蓝牙开发入门

BLE 蓝牙设备在生活中无处不在&#xff0c;但是我们也只是将其作为蓝牙模块进行使用&#xff0c;发送简单的AT命令实现数据收发。 那么&#xff0c;像对于一些复杂的使用场合&#xff1a;“车载蓝牙”、"智能手表"、“蓝牙音箱”等&#xff0c;我们不得不去了解底层…...

07:进阶篇 - 在程序中嵌入 CTK Plugin Framework

作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 如果已经创建了一个应用程序,现在要将 CTK Plugin Framework 嵌入其中,该如何进行呢? 下面,以《06:进阶篇 - Hello,CTK!》中的插件为例,来演示如何使用 CTK Plugin Framework 来加载插件并获取特定…...

快速低成本动画视频课

快速低成本动画视频课Character Animator能做什么如何用character animator制作动画视频Animate能做什么Adobe Animate和Character Animator结合&#xff0c;如何快速制作低成本动画视频课Character Animator能做什么 Character Animator是Adobe公司的一个动画制作软件&#x…...

大数据平台测试-软件测试常见面试回答(持续更新)

面试造航母&#xff0c;入职拧螺丝。面试&#xff0c;讲点面试官想听的。。。 1、你有过漏测的经历吗&#xff1f; 答&#xff1a;这道题肯定是回答有。然后展开描述。就类似面试官问 你印象比较深的一个bug。。。 测试无穷尽&#xff0c;质量也并非测试一个岗位的责任&…...

链表学习之反转链表

链表解题技巧 额外的数据结构&#xff08;哈希表&#xff09;&#xff1b;快慢指针&#xff1b;虚拟头节点&#xff1b; 反转链表 分别实现单向链表和双向链表的反转。 要求&#xff1a;长度为N的链表&#xff0c;时间复杂度为O(N)&#xff0c;额外空间复杂度为O(1)。 反转…...

ONNXRUNTUIME实例分割网络说明

ONNXRUNTUIME c使用&#xff08;分割网络&#xff09;与相关资料&#xff08;暂记&#xff09; initiate a env with an id name(使用id名称启动env) create session (创建会话 ) onnxenv -> sessioninputname [“x”] ,outputname [“t”]inputnodedim [[1,1,192,192…...

几行代码,就写完懒加载啦?

Ⅰ、前言 「懒加载」是网页中非常 常见的&#xff1b;为了减少系统的压力&#xff0c;对于一些电商系统出场频率非常高&#xff1b;那么大家一般用什么方式去实现 「懒加载」 呢 &#xff1f; ① 通过 scroll 的形式&#xff1a; 通过 滚动「scroll」事件&#xff0c;然后去判…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

如何通过git命令查看项目连接的仓库地址?

要通过 Git 命令查看项目连接的仓库地址&#xff0c;您可以使用以下几种方法&#xff1a; 1. 查看所有远程仓库地址 使用 git remote -v 命令&#xff0c;它会显示项目中配置的所有远程仓库及其对应的 URL&#xff1a; git remote -v输出示例&#xff1a; origin https://…...

虚幻基础:角色旋转

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 文章目录 移动组件使用控制器所需旋转&#xff1a;组件 使用 控制器旋转将旋转朝向运动&#xff1a;组件 使用 移动方向旋转 控制器旋转和移动旋转 缺点移动旋转&#xff1a;必须移动才能旋转&#xff0c;不移动不旋转控制器…...