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

【回眸】剑指offer(二)解题思路

题解 | #数字在升序数组中出现的次数#

JZ3数字在升序数组中出现的次数

描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ,要求统计 k 在数组中出现的次数

数据范围:0≤n≤1000,0≤k≤100,数组中每个元素的值满足 0≤val≤100
要求:空间复杂度 O(1),时间复杂度 O(logn)

输入:

[1,2,3,3,3,3,4,5],3

返回值:

4

 做题思路

函数名为GetNumberOfK。函数接受三个参数:data是一个整型数组指针,dataLen是数组的长度,k是要查找的目标值。 函数的目标是统计数组中目标值k出现的次数,并返回该次数。函数的实现思路如下: 初始化变量mid、start和end,分别表示当前搜索范围的中间位置、起始位置和结束位置。 初始化变量left和right,分别表示目标值k的左边界和右边界。 使用二分查找的思路,在数组中找到目标值k的任意一个位置。 如果data[mid]大于k,将end更新为mid。 如果data[mid]小于k,将start更新为mid。 如果data[mid]等于k,表示找到目标值,将left和right初始化为mid。 在找到目标值的位置后,分别向左和向右遍历数组,找到目标值k的左边界和右边界。 当data[left]等于k时,向左移动left。 当data[right]等于k时,向右移动right。 返回右边界right减去左边界left再减去1,即为目标值k在数组中出现的次数。

C语言代码 

/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums int整型一维数组* @param numsLen int nums数组长度* @param k int整型* @return int整型*/
#include <stdio.h>
#include <stdlib.h>int GetNumberOfK(int* data, int dataLen,int k ) {  //先找到目标target值的任意一个位置,再分别往左往右找int mid = 0;int start = 0;int end = dataLen - 1;int left = 0 ;int right = 1;for (int i = start; i <= end; i++) {mid = (start + end) / 2;if (data[mid] > k) {end = mid;}if (data[mid] < k) {start = mid;}if (data[mid] ==k) {                                         //找到值的时候break;left = mid;right = mid;printf("mid=%d\n", mid);while (data[left] == k) {left--;}while (data[right] == k) {right++;}printf("left=%d right=%d\n", left, right);break;}}return right - left - 1;
}

相关文章:

【回眸】剑指offer(二)解题思路

题解 | #数字在升序数组中出现的次数# JZ3数字在升序数组中出现的次数 描述 给定一个长度为 n 的非降序数组和一个非负数整数 k &#xff0c;要求统计 k 在数组中出现的次数 数据范围&#xff1a;0≤n≤1000,0≤k≤100&#xff0c;数组中每个元素的值满足 0≤val≤100 要求…...

Python 基本文件操作及os库

内置函数文件操作 python内置函数提供了简单的文件操作支持。 open() open()函数打开一个文件&#xff0c;创建一个file对象&#xff0c;相关的方法才可以调用它进行读写。 语法为&#xff1a; open(file,moder,buffering-1,encodingNone,errorsNone,newlineNone,closefdT…...

YOLOv5算法改进(9)— 替换主干网络之ShuffleNetV2

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。ShuffleNetV2 是一种轻量级的神经网络架构&#xff0c;适用于移动设备和嵌入式设备等资源受限的场景&#xff0c;旨在在计算资源有限的设备上提供高效的计算和推理能力&#xff0c;它通过引入通道重排操作和逐点组卷积来减…...

三、mycat分库分表

第五章 分库分表 一个数据库由很多表的构成&#xff0c;每个表对应着不同的业务&#xff0c;垂直切分是指按照业 务将表进行分类&#xff0c;分布到不同 的数据库上面&#xff0c;这样也就将数据或者说压力分担到不同 的库上面&#xff0c;如下图&#xff1a; 系统被切分成了&…...

gitlab提交项目Log in with Access Token错误

目录 报错信息 问题描述 解决方案 报错信息 问题描述 在提交项目到gitlab时&#xff0c;需要添加账户信息 &#xff0c;但是报了这样一个错&#xff0c;原因应该就是路径问题&#xff0c;我在填写server地址的时候&#xff0c;就出现了路径问题&#xff0c;我把多余的几个/…...

openGauss学习笔记-56 openGauss 高级特性-DCF

文章目录 openGauss学习笔记-56 openGauss 高级特性-DCF56.1 架构介绍56.2 功能介绍56.3 使用示例 openGauss学习笔记-56 openGauss 高级特性-DCF DCF全称是Distributed Consensus Framework&#xff0c;即分布式一致性共识框架。DCF实现了Paxos、Raft等解决分布式一致性问题典…...

Xcode 14 pod init报错

文章目录 1.报错2.解决方法&#xff08;本人亲测有效&#xff09; 1.报错 [!] Oh no, an error occurred. Search for existing GitHub issues similar to yours: https://github.com/CocoaPods/CocoaPods/search?q%5BXcodeproj%5DUnknownobjectversion%2856%29.&typeIs…...

飞腾PSPA可信启动--2 数字签名证书

今天继续第二章&#xff0c;数字签名证书的介绍。 此章节录制了讲解视频&#xff0c;可以在B站进行观看&#xff1a;...

微前端:重塑大型项目的前沿技术

引言 随着互联网技术的飞速发展&#xff0c;前端开发已经从简单的页面制作逐渐转变为复杂的应用开发。在这个过程中&#xff0c;传统的前端开发模式已经难以满足大型项目的需求。微前端作为一种新的前端架构模式&#xff0c;应运而生&#xff0c;它旨在解决大型项目中的前端开…...

官方推荐使用的OkHttp4网络请求库全面解析(Android篇)

作者&#xff1a;cofbro 前言 现在谈起网络请求&#xff0c;大家肯定下意识想到的就是 okhttp 或者 retrofit 这样的三方请求库。诚然&#xff0c;现在有越来越多的三方库帮助着我们快速开发&#xff0c;但是对于现在的程序员来说&#xff0c;我们不仅要学会如何去用&#xff…...

Spooling的原理

脱机技术 程序猿先用纸带机把自己的程序数据输入到磁带中&#xff0c;这个输入的过程是由一台专门的外围控制机实现的。之后CPU直接从快速的磁带中读取想要的这些输入数据。输出也类似。 假脱机技术&#xff08;Spooling技术&#xff09; 即用软件的方式来模拟脱机技术。要…...

Homebrew 无法安装过时的PHP版本

使用brew安装过时的PHP版本时&#xff0c;提示“Error: php7.4 has been disabled because it is a versioned formula!”错误。 因为过时的PHP版本官方已经不再维护&#xff0c;所以Hombrew将该PHP版本移出了repository&#xff0c;所以安装不了。 解决方案 # 1. 添加tap fo…...

python爬取bilibili,下载视频

一. 内容简介 python爬取bilibili&#xff0c;下载视频 二. 软件环境 2.1vsCode 2.2Anaconda version: conda 22.9.0 2.3代码 链接&#xff1a;https://pan.baidu.com/s/1WuXTso_iltLlnrLffi1kYQ?pwd1234 三.主要流程 3.1 下载单个视频 代码 import requests impor…...

java八股文面试[多线程]——进程与线程的区别

定义 1、进程&#xff1a;进程是一个具有独立功能的程序关于某个数据集合的以此运行活动。 是系统进行资源分配和调度的独立单位&#xff0c;也是基本的执行单元。是一个动态的概念&#xff0c;是一个活动的实体。它不只是程序的代码&#xff0c;还包括当前的活动。 进程结构…...

SpringBootWeb 登录认证[Cookie + Session + Token + Filter + Interceptor]

目录 1. 登录功能 1.1 需求 1.2 接口文档 1.3 登录 - 思路分析 1.4 功能开发 1.5 测试 2. 登录校验 2.1 问题分析 什么是登录校验&#xff1f; 我们要完成以上登录校验的操作&#xff0c;会涉及到Web开发中的两个技术&#xff1a; 2.2 会话技术 2.2.1 会话技术介绍…...

d3dcompiler_43.dll丢失怎么修复,分享几种修复d3dcompiler_43.dll的方法

不少人可能看到d3dcompiler_43.dll这个文件会感觉到陌生&#xff0c;是的&#xff0c;因为这个文件一般来说是很少丢失的&#xff0c;但是还是会出现d3dcompiler_43.dll丢失的情况的&#xff0c;今天主要是来给大家详细的说说d3dcompiler_43.dll丢失怎么修复的相关方法。 一.分…...

mqtt集群搭建并使用nginx做负载均衡_亲测得结论

mqtt集群搭建 RabbitMQ集群搭建和测试总结_亲测 搭建好RabbitMQ集群,并开启mqtt插件功能,mqtt集群也就搭建好了 nginx配置mqtt负载均衡 #修改rabbitmq1节点ip为1.19的nginx配置 vim /etc/nginx/nginx.confhttp { } #在http外添加如下配置 stream {upstream rabbitmqtt {ser…...

JavaScript—DOM(文档对象模型)

目录 DOM是什么&#xff1f; DOM有什么作用&#xff1f; 一、事件 理解事件 事件怎么写&#xff08;要做什么就写什么&#xff09;&#xff1f; 实战演练 1、页面加载完毕以后&#xff0c;打印一句话 2、如果有一个a标签&#xff0c;并给其添加一个点击事件 3、事件默…...

mysql Index

创建索引 方法1 create table 表( col1 int, col2 int, … index | key index_name (列名) 方法2 alter table 表名 ADD index alter table student_table add index index_name(stu_id); 方法3 create index index_name on 表名(列) 删除索引 方式1 alter table xx drop prima…...

​八路参考文献:[八一新书]许少辉.乡村振兴战略下传统村落文化旅游设计[M]北京:中国建筑出版传媒,2022.

​八路参考文献&#xff1a;&#xff3b;八一新书&#xff3d;许少辉&#xff0e;乡村振兴战略下传统村落文化旅游设计&#xff3b;&#xff2d;&#xff3d;北京&#xff1a;中国建筑出版传媒&#xff0c;&#xff12;&#xff10;&#xff12;&#xff12;&#xff0e;...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版

1.题目描述 2.思路 当前的元素可以重复使用。 &#xff08;1&#xff09;确定回溯算法函数的参数和返回值&#xff08;一般是void类型&#xff09; &#xff08;2&#xff09;因为是用递归实现的&#xff0c;所以我们要确定终止条件 &#xff08;3&#xff09;单层搜索逻辑 二…...

门静脉高压——表现

一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构&#xff1a;由肠系膜上静脉和脾静脉汇合构成&#xff0c;是肝脏血液供应的主要来源。淤血后果&#xff1a;门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血&#xff0c;引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...