当前位置: 首页 > 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;然后去判…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...