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

力扣DAY63-67 | 热100 | 二分：搜索插入位置、搜索二维矩阵、排序数组查找元素、搜索旋转排序数组、搜索最小值

news 来源：原创 2025/7/5 21:57:12

前言

简单、中等 √ 二分法思路很简单，但是判断边界太麻烦了！难道真的要去背模板吗

搜索插入位置

我的题解

循环条件左不超过右，目标大于中间值（向下取整）时，左=中+1，小于，右=中-1，否则直接返回mid，出循环后返回left。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int mid;while (left <= right){mid = ((right - left) >> 1) + left;if (target > nums[mid]){left = mid + 1;}else if (target < nums[mid]){right = mid - 1;}else{return mid;}  }return left;}
};

官方题解

官解的条件：目标大于中间值时left也++，最后返回left

心得

标准的就是简洁优雅！不对称的原因在于求mid也是不对称的：向下取整。

搜索二维矩阵

此题之前做过一模一样的，不赘述。

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

我的题解

用二分法查找到这个元素之后，向两边扩展直到不等于目标值为止。

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.empty())return{-1, -1};int n = nums.size();int left = 0;int right = n-1;while (left < right){int mid = (left + right)/2;if (target > nums[mid])left = mid + 1;else if (target < nums[mid])right = mid - 1;else{left = mid;break;}}if (left >= n || target != nums[left])return{-1, -1};right = left;while (left > 0 && nums[left-1] == target){left--;}while (right < (n-1) && nums[right+1] == target){right++;}return {left, right};}
};

官方题解

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标，但这个方法的时间复杂度为 O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 target 开始和结束位置，其实我们要找的就是数组中「第一个等于 target 的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）。

二分查找中，寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标，寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 nums 数组中二分查找 target 的位置，如果 lower 为 true，则查找第一个大于等于 target 的下标，否则查找第一个大于 target 的下标。

最后，因为 target 可能不存在数组中，因此我们需要重新校验我们得到的两个下标 leftIdx 和 rightIdx，看是否符合条件，如果符合条件就返回 [leftIdx,rightIdx]，不符合就返回 [−1,−1]

class Solution { 
public:int binarySearch(vector<int>& nums, int target, bool lower) {int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();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;}vector<int> searchRange(vector<int>& nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {return vector<int>{leftIdx, rightIdx};} return vector<int>{-1, -1};}
};

心得

原来我的题解在极端情况下不是log（n），例如整个数组都是target的情况下。所以还是官解好一点（其实也不一定，n不一定比2log（n）大）。anyway其实官解先定义一个函数找目标值，不同的是多定义了一个bool变量控制right指针的移动/等号条件，当bool为true时，找的是第一个大于等于target的位置，false时找的时第一个大于target的位置。仔细想还挺有意思！

搜索旋转排序数组

我的题解

事实上我是先写了寻找最小值再写这题。找到了最小值坐标后相当于找到了两段有序数组，分别对两段有序数组进行二分查找即可。

class Solution {
public:int findtarget(vector<int> nums, int left, int right, int target){int mid;while(left < right){mid = (right - left)/2 + left;if (target > nums[mid]){left = mid + 1;}else if (target < nums[mid]){right = mid - 1;}else{left = mid;break;}}if(nums[left] == target)return left;elsereturn -1;}int search(vector<int>& nums, int target) {int n = nums.size();int low = 0;int high = n - 1;int mid = ((high - low)>>1) + low;while (low < high){mid = ((high - low)>>1) + low;if (nums[mid] < nums[high]){high = mid;}else if (nums[mid] > nums[high]){low = mid + 1;}else{break;}}return max (findtarget(nums, low, n-1, target), findtarget(nums, 0, low-1, target));}
};

官方题解

对于有序数组，可以使用二分查找的方法查找元素。

但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

class Solution {
public:int search(vector<int>& nums, int target) {int n = (int)nums.size();if (!n) {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;}
};

心得

官解的逻辑是，中点哪边是有序的，在有序的一边判断target是否在这个区间内，如果在则把一边的边界移到这个区间中，否则把两个边界都移出区间并重复上述步骤。此题重点在于通过判断target是否在有序区间内从而缩小范围。感觉有点低估二分法了，能变形好多解法啊！！

寻找旋转排序数组中的最小值

我的题解

如果左区间有序，移动右指针，如果右区间有序移动左指针，直到两个指针相遇。写得好乱...

class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int left = 0;int right = n - 1;int mid = ((right - left)>>1) + left;int ans = nums[left];while (left < right){ans = min(ans, nums[mid]);ans = min(ans, nums[left]);if (nums[mid] < nums[left] && nums[mid] < nums[right]){right = mid - 1;mid = (mid + left - 1)/2;}else if (nums[mid] > nums[left] && nums[mid] > nums[right]){left = mid + 1;mid = (mid + right + 1)/2;}else{break;}}return min(ans, nums[right]);}
};

官方题解

一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。

我们考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。

在二分查找的每一步中，左边界为 low，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较，可能会有以下的三种情况：

第一种情况是 nums[pivot]<nums[high]。如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

第二种情况是 nums[pivot]>nums[high]。如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot 就不会与 high 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]=nums[high] 的情况。

当二分查找结束时，我们就得到了最小值所在的位置。

class Solution {
public:int findMin(vector<int>& nums) {int low = 0;int high = nums.size() - 1;while (low < high) {int pivot = low + (high - low) / 2;if (nums[pivot] < nums[high]) {high = pivot;}else {low = pivot + 1;}}return nums[low];}
};

心得

自己写得真是乱七八糟，官解就优雅很多。当右边比较大的时候说明右区间有序，最小值在左区间，收窄右区间（中间值有可能最小，故不越界），否则说明右区间无序，最小值在右区间，收窄左区间（中间值不可能为最小，故越界）。另外由于中间值是向下取整且循环条件是小于，故不可能等于右指针，所以无需考虑中间值=右边的情况。

二分的思想在于每次淘汰一半！！

力扣DAY63-67 | 热100 | 二分：搜索插入位置、搜索二维矩阵、排序数组查找元素、搜索旋转排序数组、搜索最小值

前言简单、中等 √ 二分法思路很简单，但是判断边界太麻烦了！难道真的要去背模板吗搜索插入位置我的题解循环条件左不超过右，目标大于中间值（向下取整）时，左中1，小于，右中-1&…...

编程日记 2025/7/5 21:57:12

leetcode-哈希表

哈希表 127. 单词接龙题目字典 wordList 中从单词 beginWord 到 endWord 的转换序列是一个按下述规格形成的序列 beginWord -> s(1) -> s(2) -> ... -> s(k)： 每一对相邻的单词只差一个字母。对于 1 < i < k 时，每个 s(i) 都在…...

编程日记 2025/7/4 8:44:33

信息技术有限公司项目管理手册

这篇文档是信息技术有限公司的项目管理指导手册，对软件公司项目管理者具有重要价值，主要体现在以下几个方面： 管理全面规范涵盖内容广：从项目的整体管理到各个具体领域，如范围管理、进度管理、成本管理等&…...

编程日记 2025/6/29 10:14:56

TFTP服务调试

在tftpboot目录下进行sudo minicom 启动内核时问题：程序启动卡在Loading阶段原因：tftp协议的问题、或者网卡配置的问题解决：1.检查网线是否插好多试几次 2.检查tftp服务是否正常在minicom中调试ping pc机的ip地址 2.进入boot调…...

编程日记 2025/7/4 6:13:48

date-picker组件的shortcuts为什么不能配置在vue的data的return中

在 Vue 中，shortcuts 是一个选项，通常用于配置像 date-picker 这样的组件的日期快捷方式。这里有一些原因解释为什么 shortcuts 不应该配置在 data 的 return 中，而是应该配置在 data 的外部（例如，直接作为组件的一个属…...

编程日记 2025/7/3 14:08:59

迭代器模式：统一数据遍历方式的设计模式

迭代器模式：统一数据遍历方式的设计模式一、模式核心：将数据遍历逻辑与数据结构解耦在软件开发中，不同的数据结构（如数组、链表、集合）有不同的遍历方式。如果客户端直接依赖这些数据结构的内部实现来遍历元素&…...

编程日记 2025/7/5 21:49:50

RocketMQ 核心架构速览

欢迎光临小站：致橡树文章现有讲述比较简单，后续逐渐丰富各部分内容。 Apache RocketMQ 作为阿里巴巴开源的一款分布式消息中间件，凭借其高吞吐、低延迟、高可用等特性，成为金融级稳定性场景的首选解决方案。本文将深入剖析 Roc…...

编程日记 2025/7/3 8:01:11

kafka安装、spark安装

kafka简介 Kafka就是一个分布式的用于消息存储的消息队列。 kafka角色 Kafka中存储的消息，被消费后不会被删除，可以被重复消费，消息会保留多长，由kafka自己去配置。默认7天删除。背后的管理工作由zookeeper来管理。 kafka安装 …...

编程日记 2025/7/3 10:05:14

迅为RK3562开发板ARM四核A53核心板多种系统适配全开源

迅为RK3562开发板ARM四核A53核心板多种系统适配全开源 RK3562开发板(2GB内存16GB存储)...

编程日记 2025/7/5 21:52:13

用交换机连接两台电脑，电脑A读取/写电脑B的数据

1、第一步，打开控制面板中的网络和共享中心，如下图配置，电脑A和电脑B均要配置； 注意：要保证电脑A和电脑B在同一子网掩码下，不同的IP地址； 2、在电脑上同时按‘CommandR’，在弹出的输…...

编程日记 2025/7/3 16:22:47

线程入门3

synchronized修饰方法 synchronized可以修饰代码块(在线程入门2中有例子)，也可以修饰普通方法和静态方法。修饰普通方法修饰普通方法简化写法： 修饰静态方法修饰静态方法简化写法： 注意：利用synchronized上锁，锁的…...

编程日记 2025/7/5 21:57:12

【C++】AVL树

目录一、AVL树的引入二、AVL树 🍔AVL树的概念 🍟AVL树节点的定义 🌮AVL树的插入 🥪AVL树的旋转三、AVL树的验证四、结语一、AVL树的引入 🌟我们知道 map/multimap/set/multiset 这几个容器的共同点是&#…...

编程日记 2025/7/3 12:48:50

Java大师成长计划之第1天：Java编程基础入门

📢 友情提示： 本文由银河易创AI（https://ai.eaigx.com）平台gpt-4o-mini模型辅助创作完成，旨在提供灵感参考与技术分享，文中关键数据、代码与结论建议通过官方渠道验证。欢迎来到“Java大师成长计划”系列文…...

编程日记 2025/7/5 13:36:43

Java线程中断机制详解

中断机制是Java中一种协作式的线程停止方式，它提供了一种优雅的线程间通信机制，用于请求另一个线程停止当前工作。中断机制的核心概念中断标志位(Interrupt Status) 每个线程都有一个boolean类型的中断状态标志（native方法控制&#xff09…...

编程日记 2025/6/29 9:25:07

gem5-gpu教程06 回归测试

gem5-gpu包括gem5风格的回归测试，以避免常见错误，并在变更集之间保持模拟系统性能的一致性。如果你想为gem5-gpu做出贡献，你必须确保你的更改通过了包含的回归测试。回归测试是一种软件测试类型，其主要目的是确保新代码的更改没有对现有功能造成影响。在软件开发过程中，当…...

编程日记 2025/6/29 11:46:44

查询Hologres或postgresql中的数据

因Hologres使用postgresql的语法.所以两者查询一样. 方案1: import java.sql.Connection; import java.sql.DriverManager; import java.sql.SQLException; import java.util.ArrayList; import java.util.List;/*** 一个使用简单连接池管理PostgreSQL连接的工具类。*/ publi…...

编程日记 2025/6/29 9:24:53

C# 文件读取

文件读取是指使用 C# 程序从计算机文件系统中获取文件内容的过程。将存储在磁盘上的文件内容加载到内存中，供程序处理。主要类型有：文本文件读取（如 .txt, .csv, .json, .xml）；二进制文件读取（如 .jpg, .pn…...

编程日记 2025/7/3 4:59:18

On the Biology of a Large Language Model——Claude团队的模型理解文章【论文阅读笔记】其一CLT与LLM知识推理

这个学习笔记，是在精读Anthropic的博客 On the Biology of a Large Language Model 的过程中留下的笔记。由于原文非常长，我会分2-3 个博客来写。作者的思路作者对常用的LLM特征解读工具 SAE/Transcoder 进行了优化，增加了跨层连接的能力…...

编程日记 2025/6/29 9:24:11

Postman忘记密码访问官网总是无响应

1.Header Editor插件下载百度网盘下载： 链接：https://pan.baidu.com/s/1EV6cY7TYQVgPjip3v-vhfQ 提取码：yyds 2.插件配置下载规则url：https://azurezeng.github.io/static/HE-GoogleRedirect.json ![在这里插入图片描述](htt…...

编程日记 2025/6/29 11:31:11

NEUOJ网格路径

在一个 77 的网格中，从左上方的方格走到左下方的方格，共有 88418 条路径。每条路径对应一个由字符 D（向下）、U（向上）、L（向左）和 R（向右）组成的 48 字符描…...

编程日记 2025/6/29 9:24:48

深度学习中的黑暗角落：梯度消失与梯度爆炸问题解析

📌 友情提示： 本文内容由银河易创AI（https://ai.eaigx.com）创作平台的gpt-4o-mini模型生成，旨在提供技术参考与灵感启发。文中观点或代码示例需结合实际情况验证，建议读者通过官方文档或实践进一步确认其准…...

编程日记 2025/7/5 10:15:05

【数字图像处理】机器视觉（1）

判别相对应的点 1. 图像灰度化 2. 局部特征 3. 仿射不变性特征图像变化的类型【1】几何变化：旋转、相似（旋转各向相同的尺度缩放）、仿射（非各向相同的尺度缩放） 【2】灰度变化：仿射灰度变化角点角…...

编程日记 2025/7/5 21:52:13

# 构建和训练一个简单的CBOW词嵌入模型

构建和训练一个简单的CBOW词嵌入模型在自然语言处理（NLP）领域，词嵌入是一种将词汇映射到连续向量空间的技术，这些向量能够捕捉词汇之间的语义关系。在这篇文章中，我们将构建和训练一个简单的Continuous Bag of Words…...

编程日记 2025/6/29 11:02:01

Ubuntu20.04下GraspNet复现流程中的问题

pytorchcudacudnn的版本问题相对于GraspNet来说至关重要！！！至关重要！！！至关重要！！！（重要的事情说三边） 我的显卡是3070 那么首先说结论使用30系…...

编程日记 2025/7/3 21:06:15

【ROS2】机器人操作系统安装到Ubuntu简介

主要参考： https://book.guyuehome.com/ROS2/1.系统架构/1.3_ROS2安装方法/ 官方文档：https://docs.ros.org/en/humble/Installation.html 虚拟机与ubuntu系统安装略，见参考文档 ubutun换国内源，略 1. 设置本地语言确保您有…...

编程日记 2025/7/4 5:01:47

从0到1掌握机器学习核心概念：用Python亲手构建你的第一个AI模型（超多代码+可视化）

🧠 一、开始真正动手实现一个完整的AI项目！从数据预处理、特征工程、模型训练，到评估与调优，一步步还原你在动画视频中看到的所有核心知识点。 📦 二、环境准备建议使用 Python 3.8，推荐工具&#xff1…...

编程日记 2025/7/4 5:49:27

Java面试题汇总

1王二哥 https://javabetter.cn/sidebar/sanfene/redis.html#_10-redis-%E6%8C%81%E4%B9%85%E5%8C%96%E6%96%B9%E5%BC%8F%E6%9C%89%E5%93%AA%E4%BA%9B-%E6%9C%89%E4%BB%80%E4%B9%88%E5%8C%BA%E5%88%AB 2.小林 https://www.xiaolincoding.com/redis/data_struct/command.html#…...

编程日记 2025/7/3 11:35:36

前言

搜索插入位置

我的题解

官方题解

心得

搜索二维矩阵

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

我的题解

官方题解

心得

搜索旋转排序数组

我的题解

官方题解

心得

寻找旋转排序数组中的最小值

我的题解

官方题解

心得

相关文章：