力扣大厂热门面试算法题 33-35

         33. 搜索旋转排序数组,34. 在排序数组中查找元素的第一个和最后一个位置 ,35. 搜索插入位置,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.15 可通过leetcode所有测试用例。

目录

33. 搜索旋转排序数组

解题思路

完整代码

Python

Java

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

解题思路

完整代码

Python

Java

35. 搜索插入位置

解题思路

完整代码

Python

Java


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 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 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

解题思路

为了在 O(log n) 的时间复杂度内解决这个问题,我们可以使用二分查找。由于数组在某个下标上进行了旋转,数组被分成了两部分,每部分都是有序的。我们的目标是确定 target 是否在有序的那部分中,如果不在,就在另一部分中查找。

具体步骤如下:

  1. 初始化:设置两个指针 leftright,分别指向数组的开始和结束。

  2. 二分查找:在 left <= right 的条件下进行循环。

    • 计算中点 mid = (left + right) / 2
    • 如果 nums[mid] 等于 target,直接返回 mid
    • 接下来判断 nums[mid]nums[left] 的关系,以确定哪部分是有序的。
      • 如果 nums[mid] >= nums[left],说明左侧是有序的。
        • 如果 targetnums[left]nums[mid] 之间,我们应该在左侧查找,将 right 更新为 mid - 1
        • 否则,在右侧查找,将 left 更新为 mid + 1
      • 否则,右侧是有序的。
        • 如果 targetnums[mid]nums[right] 之间,我们应该在右侧查找,将 left 更新为 mid + 1
        • 否则,在左侧查找,将 right 更新为 mid - 1
  3. 返回结果:如果循环结束后还没有找到 target,返回 -1

完整代码

Python
class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return mid# 判断左侧是否是有序的if nums[left] <= nums[mid]:# 如果目标值在左侧的有序区间内if nums[left] <= target < nums[mid]:right = mid - 1else:left = mid + 1else:# 右侧是有序的if nums[mid] < target <= nums[right]:left = mid + 1else:right = mid - 1return -1
Java
public class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;}if (nums[mid] >= nums[left]) {// 左边是有序的if (target >= nums[left] && target < nums[mid]) {right = mid - 1;  // target 在左边} else {left = mid + 1;  // target 在右边}} else {// 右边是有序的if (target > nums[mid] && target <= nums[right]) {left = mid + 1;  // target 在右边} else {right = mid - 1;  // target 在左边}}}return -1;  // 没有找到 target}
}

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]

解题思路

        为了在 O(log n) 的时间复杂度内解决这个问题,我们可以使用二分查找的变种来分别找到目标值的开始位置和结束位置。这个方法包括两次二分查找:

  1. 查找开始位置:修改二分查找,使其在找到目标值时继续向左搜索,以找到目标值的最左侧索引。
  2. 查找结束位置:再次使用二分查找,但这次在找到目标值时继续向右搜索,以找到目标值的最右侧索引。

完整代码

Python
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def binarySearchLeft(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] < target:left = mid + 1else:right = mid - 1return leftdef binarySearchRight(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] <= target:left = mid + 1else:right = mid - 1return rightstart = binarySearchLeft(nums, target)end = binarySearchRight(nums, target)if start <= end:return [start, end]else:return [-1, -1]
Java
public class Solution {public int[] searchRange(int[] nums, int target) {int[] result = new int[]{-1, -1};result[0] = binarySearchLeft(nums, target);result[1] = binarySearchRight(nums, target);if (result[0] <= result[1]) {return result;}return new int[]{-1, -1};}private int binarySearchLeft(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;}private int binarySearchRight(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}return right;}
}

35. 搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

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

解题思路

  1. 初始化指针:设置两个指针 leftright,分别指向数组的开始和结束。

  2. 二分查找:当 left <= right 时,计算中点 mid = (left + right) / 2,并比较 nums[mid]target

    • 如果 nums[mid] 等于 target,直接返回 mid 作为目标值的索引。
    • 如果 nums[mid] 小于 target,则 target 应该在 mid 右侧,所以设置 left = mid + 1
    • 如果 nums[mid] 大于 target,则 target 应该在 mid 左侧,所以设置 right = mid - 1
  3. 返回插入位置:如果循环结束仍没有找到 target,那么 target 应该被插入在 left 指针当前的位置,此时 left 指针指向了数组中第一个大于 target 的元素位置,或者是数组的末尾。

完整代码

Python
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1return left
Java
public class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;}
}

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

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

相关文章

SpringController返回值和异常自动包装

今天遇到一个需求&#xff0c;在不改动原系统代码的情况下。将Controller的返回值和异常包装到一个统一的返回对象中去。 例如原系统的接口 public String myIp(ApiIgnore HttpServletRequest request);返回的只是一个IP字符串"0:0:0:0:0:0:0:1"&#xff0c;目前接口…

一款比 K8S 更好用的编排工具——Nomod

今天给笔友们推荐一款最近发现的服务编排工具Nomad。综合感觉就是功能很强大&#xff0c;姿势很优雅&#xff0c;相比 K8S 更加轻量级&#xff0c;相比 Docker-Compose 能轻松支持分布式。 Nomad 能做什么&#xff1f; Nomad 采用统一的工作流程&#xff0c;既可以轻松部署和管…

20 OpenCV像素重映

文章目录 像素重映remap 重映算子代码示例 像素重映 简单点说就是把输入图像中各个像素按照一定的规则映射到另外一张图像的对应位置上去&#xff0c;形成一张新的图像。 g(x,y)是重映射之后的图像&#xff0c;h(x,y)是功能函数&#xff0c;f是源图像 remap 重映算子 Remap…

高效备考2025年AMC8竞赛:吃透2000-2024年600道真题(免费送题)

我们继续来随机看五道AMC8的真题和解析&#xff0c;根据实践经验&#xff0c;对于想了解或者加AMC8美国数学竞赛的考生来说&#xff0c;吃透AMC8历年真题是备考更加科学、有效的方法之一。 即使不参加AMC8竞赛&#xff0c;吃透了历年真题600道和背后的知识体系&#xff0c;那么…

阳光保险MySQL数据库平稳迁移OceanBase,稳定运营超700天

作者简介&#xff1a; 车东兴&#xff1a;于阳光保险就职&#xff0c;深耕保险行业的 IT 领域长达12 年&#xff0c;对保险领域的基础架构实践有深刻的理解与掌握。熟悉多款数据库&#xff0c;具有丰富的数据库运维经验。 王华城&#xff1a;于阳光保险就职&#xff0c;10多年一…

线性表——单链表的增删查改

本节复习链表的增删查改 首先&#xff0c; 链表不是连续的&#xff0c; 而是通过指针联系起来的。 如图&#xff1a; 这四个节点不是连续的内存空间&#xff0c; 但是彼此之间使用了一个指针来连接。 这就是链表。 现在我们来实现链表的增删查改。 目录 单链表的全部接口…

Swift:.ignoresSafeArea():自由布局的全方位掌握

ignoresSafeArea(_ regions : edges:)修饰符的说明 SwiftUI布局系统会调整视图的尺寸和位置&#xff0c;以避免特定的安全区域。这就确保了系统内容&#xff08;比如软件键盘&#xff09;或设备边缘不会遮挡您的视图。要将您的内容扩展到这些区域&#xff0c;您可以通过应用该修…

Python - 应用篇 :ChatGPT +Pycharm 序列号自动生成

前言&#xff1a; 客户要求在产品外壳上新增可追溯的二维码贴花&#xff0c;二维码信息内容如下&#xff1a; 编码格式&#xff1a;SBD 零部件代码 控制盒序列号 控制盒厂家 例如&#xff1a;[)>06P725-18428S24031410001ZJL SBD 零部件代码&#xff1a;[)>06P725-184…

【办公类-40-02】20240311 python模仿PPT相册功能批量插入照片,更改背景颜色 (家长会系列二)

作品展示——用Python插入PPT相册 背景需求&#xff1a; 马上就要家长会&#xff0c;我负责做会议前的照片滚动PPT&#xff0c;通常都是使用PPT的相册功能批量导入照片&#xff0c; 生成给一个新的PPT文件 更改背景颜色 设置4秒间隔&#xff0c;应用到全部 保存&#xff0c;改…

linux板子vscode gdb 远程调试

板子&#xff1a;hi3556v200 交叉编译工具&#xff1a;arm-himix200-linux 主机&#xff1a;win10虚拟机的ubuntu16.4 gdb:gdb-8.2.tar.gz 1.在ubuntu交叉编译gdb&#xff08;Remote g packet reply is too long解决&#xff09; 建议修改gdb8.2/gdb目录下面的remote.c解决…

git的实际运用

1. SSH配置和Github仓库克隆 注意博主在这里演示的SSH密钥生成方式&#xff0c;下面追加的五行不成功时可手动到.ssh下的config文件中添加即可 $ tail -5 config Host github.comHostName github.comPreferredAuthentications publickeyIdentityFile ~/.ssh/test 演示 2. 关联…

YoloV7改进策略:下采样改进|HWD改进下采样

摘要 本文使用HWD改进下采样&#xff0c;在YoloV7的测试中实现涨点。 论文解读 在卷积神经网络&#xff08;CNNs&#xff09;中&#xff0c;极大池化或跨行卷积等下采样操作被广泛用于聚合局部特征、扩大感受野和最小化计算开销。然而&#xff0c;对于语义分割任务&#xff…

C++手写链表、反转链表、删除链表节点、遍历、为链表增加迭代器

本篇博客介绍如何使用C实现链表&#xff0c;首先编写一个简单的链表&#xff0c;然后增加模板&#xff0c;再增加迭代器。 简单链表的实现 链表的结构如下&#xff1a; 首先需要定义链表的节点&#xff1a; struct ListNode {int data;ListNode* pNext;ListNode(int value …

使用STM32+ESP8266(ESP-01S)+点灯科技(手机端Blinker)实现远程控制智能家居

硬件准备&#xff1a;STM32单片机、ESP8266&#xff08;ESP-01S&#xff09;、CH340C下载烧录器 软件准备&#xff1a;STM32CubeMX、Keil uVision5、Arduino IDE、 点灯科技&#xff08;手机端APP Blinker&#xff09;点灯科技 (diandeng.tech)点击进入 值得注意的是&#x…

Redis:ClassCastException【bug】

Redis&#xff1a;ClassCastException【bug】 前言版权Redis&#xff1a;ClassCastException【bug】错误产生相关资源控制器&#xff1a;UserController("/user")配置&#xff1a;RedisConfiguration实体类&#xff1a;User数据表&#xff1a;User 解决 最后 前言 2…

R语言语法基础(说人话版)

在Rstudio中使用ctrl回车来执行某一行的代码 在R语言中&#xff0c;通常不需要像C语言一样在每条语句的结尾添加分号来表示语句结束。R语言是一种脚本语言&#xff0c;它使用换行符来分隔语句&#xff0c;因此分号通常是可选的&#xff0c;除非你想在同一行上写多个语句。在R中…

03-java基础-运算符(数据类型转换)、原码、补码、反码

一、运算符 一、1、算术运算符 在代码中如果有小数参与运算&#xff0c;结果有可能会不精确。 一、1.1、数字相加 一、1.1.1、类型转换的分类&#xff08;2种&#xff09; 一、1.1.1.1、类型转换的分类1-----隐式转换 一、1.1.1.1、类型转换的分类2-----强制转换 一、1.2、字符…

EtherCAT开源主站 IGH 介绍及主站伺服控制过程

目录 前言 IGH EtherCAT主站介绍 主要特点和功能 使用场景 SOEM 主站介绍 SOEM 的特点和功能 SOEM 的使用场景 IGH 主站 和 SOEM对比 1. 功能和复杂性 2. 资源消耗和移植性 3. 使用场景 EtherCAT 通信原理 EtherCAT主站控制伺服过程 位置规划模式 原点复归模式…

ASP.NET Mvc+FFmpeg+Video实现视频转码

目录 首先&#xff0c;做了视频上传的页面&#xff1a; FFmpeg&#xff1a;视频转码 FFmpegHelper工作类&#xff1a; 后台控制器代码&#xff1a; 前端视图代码&#xff1a; 参考文章&#xff1a; 首先&#xff0c;做了视频上传的页面&#xff1a; 借鉴了这篇文章 ASP.…

应用层_HTTPHTTPS

在应用层中&#xff0c;协议一般是程序员定制的&#xff0c;但现在已经有了许多非常好用的协议&#xff0c;我们可以直接参考使用。其中http和https便是其中最常用的协议之一。 一.HTTP 超文本传输协议&#xff08;Hypertext Transfer Protocol&#xff0c;HTTP&#xff09;…