第 1 天_二分查找【算法基础】

第 1 天_二分查找

  • 前言
  • 34. 在排序数组中查找元素的第一个和最后一个位置
  • 题解
  • 官方
  • 33. 搜索旋转排序数组
  • 题解
  • 官方
  • 74. 搜索二维矩阵

前言

这是陈旧已久的草稿2021-11-09 19:33:44

当时在学习数据结构,然后再LeetCode上找了一个算法基础。
但是后来又没做了。

现在2024-5-12 22:03:18,发布到[LeetCode]专栏中。

34. 在排序数组中查找元素的第一个和最后一个位置

难度 中等
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

进阶:

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:

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

示例 2:

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

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

题解

思路:左右指针
因为数组nums是升序给出的
class Solution {public int[] searchRange(int[] nums, int target) {int [] searchRange=new int[2];int left=0;int right=nums.length-1;boolean findL=false;boolean findR=false;while((!findL||!findR)&&(left<=right)){if(!findL){if(nums[left]==target){findL=true;searchRange[0]=left;}else{left++;}}if(!findR){if(nums[right]==target){findR=true;searchRange[1]=right;}else{right--;}}}if (!findL&&!findR){searchRange[0]=-1;searchRange[1]=-1;}return searchRange;}
}

在这里插入图片描述

官方

 思路:二分查找
class Solution {public int[] searchRange(int[] nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {return new int[]{leftIdx, rightIdx};} return new int[]{-1, -1};}public int binarySearch(int[] nums, int target, boolean lower) {int left = 0, right = nums.length - 1, ans = nums.length;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}
}作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

33. 搜索旋转排序数组

难度 中等
整数数组 nums 按升序排列,数组中的值 互不相同

在传递给函数之前,nums 在预先未知的某个下标 k0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1

示例 1:

输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4

示例 2:

输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1

示例 3:

输入:nums = [1], target = 0
输出:-1

提示:

  • 1 <= nums.length <= 5000
  • -104<= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

进阶:你可以设计一个时间复杂度为 O(log n) 的解决方案吗?

题解

思路:左右指针
class Solution {public int search(int[] nums, int target) {int left=0;int rigth=nums.length-1;while(left<=rigth){if(nums[left]==target){return left;}if(nums[rigth]==target){return rigth;}left++;rigth--;}return -1;}
}

在这里插入图片描述

官方

思路:二分查找
class Solution {public int search(int[] nums, int target) {//最简单问题int n = nums.length;if (n == 0) {return -1;}if (n == 1) {return nums[0] == target ? 0 : -1;}//普通int l = 0, r = n - 1;//二分法while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) {return mid;}if (nums[0] <= nums[mid]) {//在前一半if (nums[0] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {l = mid + 1;} else {r = mid - 1;}}}return -1;}
}作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

在这里插入图片描述

74. 搜索二维矩阵

难度 中等
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true

示例 2:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104
思路
因为每行的第一个整数大于前一行的最后一个整数。
所以先要从第一列找
找出target在哪一列

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/327561.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【考古篇】Attension is all you need

Transformer 文章目录 Transformer1. What2. Why3. How3.1 Encoder3.2 Decoder3.3 Attention3.4 Application3.5 Position-wise Feed-Forward Networks(The second sublayer)3.6 Embeddings and Softmax3.7 Positional Encoding3.8 Why Self-Attention 1. What A new simple n…

最新极空间部署iCloudpd教程,实现自动同步iCloud照片到NAS硬盘

【iPhone福利】最新极空间部署iCloudpd教程&#xff0c;实现自动同步iCloud照片到NAS硬盘 哈喽小伙伴们好&#xff0c;我是Stark-C~ 我记得我前年的时候发过一篇群晖使用Docker部署iCloudpd容器来实现自动同步iCloud照片的教程&#xff0c;当时热度还很高&#xff0c;可见大家…

CSS表格特殊样式

列组样式 使用colgroup与col标签配合可以定义列祖样式&#xff1a;例 <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title><style>table,tr,th,td{border: 1px solid #000;}table{border-collapse: coll…

【数据结构】顺序表与链表的差异

顺序表和链表都是线性表&#xff0c;它们有着相似的部分&#xff0c;但是同时也有着很大的差异。 存储空间上的差异&#xff1a; 对于插入上的不同点&#xff0c;顺序表在空间不够时需要扩容&#xff0c;而如果在使用realloc函数去扩容&#xff0c;会有原地扩容和异地扩容两种情…

Python图形复刻——绘制母亲节花束

各位小伙伴&#xff0c;好久不见&#xff0c;今天学习用Python绘制花束。 有一种爱&#xff0c;不求回报&#xff0c;有一种情&#xff0c;无私奉献&#xff0c;这就是母爱。祝天下妈妈节日快乐&#xff0c;幸福永远&#xff01; 图形展示&#xff1a; 代码展示&#xff1a; …

GCP谷歌云有什么数据库类型,该怎么选择

GCP谷歌云提供的数据库类型主要包括&#xff1a; 关系型数据库&#xff1a;这类数据库适用于结构化数据&#xff0c;通常用于数据结构不经常发生变化的场合。在GCP中&#xff0c;关系型数据库选项包括Cloud SQL和Cloud Spanner。Cloud SQL提供托管的MySQL、PostgreSQL和SQL Se…

GPT-4o正式发布;零一万物发布千亿参数模型;英国推出AI评估平台

OpenAI 正式发布 GPT-4o 今天凌晨&#xff0c;OpenAI 正式发布 GPT-4o&#xff0c;其中的「o」代表「omni」&#xff08;即全面、全能的意思&#xff09;&#xff0c;这个模型同时具备文本、图片、视频和语音方面的能力&#xff0c;甚至就是 GPT-5 的一个未完成版。 并且&…

RK3566(泰山派):3.1寸屏幕D310T9362V1SPEC触摸驱动(竖屏)

RK3566&#xff08;泰山派&#xff09;&#xff1a;3.1寸屏幕D310T9362V1SPEC触摸驱动&#xff08;竖屏&#xff09; 文章目录 RK3566&#xff08;泰山派&#xff09;&#xff1a;3.1寸屏幕D310T9362V1SPEC触摸驱动&#xff08;竖屏&#xff09;电路配置i2c1设备树创建驱动编写…

【Qt】常用控件(一)

文章目录 一、核心属性1、enabled代码示例: 通过按钮2 切换按钮1 的禁用状态 2、geometry代码示例: 控制按钮的位置代码示例&#xff1a;window frame 的影响代码示例: 感受 geometry 和 frameGeometry 的区别 3、windowTitle4、windowIcon代码示例: 通过 qrc 管理图片作为图标…

【ARM Cortex-M 系列 2.3 -- Cortex-M7 Debug event 详细介绍】

请阅读【嵌入式开发学习必备专栏】 文章目录 Cortex-M7 Debug eventDebug events Cortex-M7 Debug event 在ARM Cortex-M7架构中&#xff0c;调试事件&#xff08;Debug Event&#xff09;是由于调试原因而触发的事件。一个调试事件会导致以下几种情况之一发生&#xff1a; 进…

76岁林子祥升级做爷爷,亲自为孙女取名

林子祥与前妻吴正元的儿子&#xff0c;现年39岁的林德信入行以来绯闻不少&#xff0c;自与圈外女友Candace拍拖后便修心养性&#xff0c;去年他已经低调与拍拖5年多Candace完婚&#xff0c;正式步入人生另一阶段。 昨日&#xff08;5月12日&#xff09;林德信借母亲节这个温馨日…

【线性系统理论】笔记一

一&#xff1a;状态空间表达式 电路系统状态空间描述列写 1&#xff1a;选取状态变量 状态变量定义&#xff1a;线性无关极大组属性。 2&#xff1a;列出电路原始回路方程 ps&#xff1a;状态变量有两个&#xff0c;理论上需要列写2个方程 3&#xff1a;规范形势 4&#xf…

两小时看完花书(深度学习入门篇)

1.深度学习花书前言 机器学习早期的时候十分依赖于已有的知识库和人为的逻辑规则&#xff0c;需要人们花大量的时间去制定合理的逻辑判定&#xff0c;可以说是有多少人工&#xff0c;就有多少智能。后来逐渐发展出一些简单的机器学习方法例如logistic regression、naive bayes等…

智慧文旅赋能旅游服务升级:以科技创新驱动行业变革,打造智慧化、个性化、高效化的旅游新体验,满足游客日益增长的多元化需求

目录 一、引言 二、智慧文旅的概念与内涵 三、智慧文旅在旅游服务升级中的应用 1、智慧旅游服务平台建设 2、智慧景区管理 3、智慧旅游营销 四、智慧文旅推动旅游行业变革的案例分析 案例一&#xff1a;某智慧旅游城市建设项目 案例二&#xff1a;某景区智慧化改造项目…

47. UE5 RPG 实现角色死亡效果

在上一篇文章中&#xff0c;我们实现了敌人受到攻击后会播放受击动画&#xff0c;并且还给角色设置了受击标签。并在角色受击时&#xff0c;在角色身上挂上受击标签&#xff0c;在c里&#xff0c;如果挂载了此标签&#xff0c;速度将降为0 。 受击有了&#xff0c;接下来我们将…

22. 括号生成

1.题目 22. 括号生成 - 力扣&#xff08;LeetCode&#xff09; 2.思路 3.代码 class Solution { public:int left,right;string path;vector<string> ret;vector<string> generateParenthesis(int n) {dfs(n);return ret;}void dfs(int n){if(rightn){ret.push_…

前端使用Compressor.js实现图片压缩上传

前端使用Compressor.js实现图片压缩上传 Compressor.js官方文档 安装 npm install compressorjs使用 在使用ElementUI或者其他UI框架的上传组件时&#xff0c;都会有上传之前的钩子函数&#xff0c;在这个函数中可以拿到原始file&#xff0c;这里我用VantUI的上传做演示 a…

在js中table表格中进行渲染轮播图

效果图&#xff1a;示例&#xff1a; <!DOCTYPE html> <html> <head><meta charset"utf-8"><title></title><script src"js/jquery-3.6.3.js"></script><style>/* 轮播图 */.basko {width: 100%;h…

【C++】string|迭代器iterator|getline|find

目录 ​编辑 string 1.string与char* 的区别 2.string的使用 字符串遍历 利用迭代器遍历 范围for遍历 反向迭代器 字符串capacity 字符串插入操作 push_back函数 append函数 运算符 ​编辑 insert函数 substr函数 字符串查找函数 find函数 rfind函数 …

【C++】priority_queues(优先级队列)和反向迭代器适配器的实现

目录 一、 priority_queue1.priority_queue的介绍2.priority_queue的使用2.1、接口使用说明2.2、优先级队列的使用样例 3.priority_queue的底层实现3.1、库里面关于priority_queue的定义3.2、仿函数1.什么是仿函数&#xff1f;2.仿函数样例 3.3、实现优先级队列1. 1.0版本的实现…