【Leetcode】top 100 二分查找

news/2024/6/15 0:13:27/文章来源:https://blog.csdn.net/qq_45430996/article/details/137194242
35 搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

基础写法!!!牢记!!!

第一个只适用与一个目标值的情况,第二个适用于多个目标值靠左取的情况(要靠右取可以找target+1获得下标值-1);

class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if target == nums[mid]:return midelif target < nums[mid]:right = mid-1else:left = mid+1return leftdef lower_bound(nums, target):left, right = 0, len(nums) - 1  # 闭区间 [left, right]while left <= right: mid = (left + right) // 2if nums[mid] < target:left = mid + 1         # 范围缩小到 [mid+1, right]else:right = mid - 1        # 范围缩小到 [left, mid-1]return left
 74 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵:

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。

方法一:二分先找列再找行    定列的时候要靠近小值(取down)

              或者将二维矩阵拉成一维矩阵然后同题35      时间复杂度相同O(logm+logn)

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""up, down = 0, len(matrix)-1while up <= down:mid = (up+down)//2if target == matrix[mid][0]: return Trueelif target < matrix[mid][0]:down = mid-1else:up = mid+1left, right = 0, len(matrix[0])-1while left <= right:mid = (left+right)//2if target == matrix[down][mid]: return Trueelif target < matrix[down][mid]:right = mid-1else:left = mid+1return False

方法二:满足题目规定的二维矩阵可以看成一棵二叉搜索树    时间复杂度O(m+n)

class Solution:def searchMatrix(self, matrix, target):m, n = len(matrix), len(matrix[0])x, y = 0, n - 1while x < m and y >= 0:if matrix[x][y] > target:y -= 1elif matrix[x][y] < target:x += 1else:return Truereturn False
34 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

两遍二分查找,第一遍找target,第二遍找target+1,都靠左取;

不存在目标值情况:目标值过小/大,idx1=0/len(nums)

                                 目标值没出现:nums[idx1] != target    (可以和idx1=0合并)

class Solution(object):def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[mid] < target:left = mid+1else:right = mid-1idx1 = leftleft, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[mid] < target+1:left = mid+1else:right = mid-1idx2 = left-1if idx1 == len(nums) or nums[idx1] != target: return [-1, -1]else: return [idx1, idx2]
33 搜索旋转排列数组

整数数组 nums 按升序排列,数组中的值 互不相同 。在传递给函数之前,nums 在预先未知的某个下标 k0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

二分出一侧排序正确的区域,若target在这个区域里,正常查找,若在排序不正确的区域里,继续二分;

因为目标值仅出现一次,可提前判断;

找不到递增区间时终止循环;

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[mid] == target: return midelif nums[left] == target: return leftelif nums[right] == target: return rightif nums[left] < nums[mid] :    # [left, mid]排序正确if nums[mid] > target and nums[left] < target:    # target在[left, mid]内  right = mid - 1else:left = mid + 1         elif nums[mid] < nums[right]:  # [mid, right]排序正确if nums[mid] < target and nums[right] > target:   # target在[mid, right]内  left = mid + 1else:right = mid - 1 else:return -1if not nums or nums[left] != target: return -1else: return left
153 寻找排序数组中的最小值

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:

  • 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

假设旋转k次,则数组为 [a[n-k],a[n-k+1],...,a[0],...,a[n-k-1]] 一次二分

情况一:nums[left] < nums[mid] < nums[right] 最小值为 nums[left]

情况二:若左侧排序正确最小值只可能在右侧区间  搜索区间为[mid+1,right]

情况三:同理右侧排序正确则最小值只可能在左侧区间 搜索区间为[left,mid]   注意mid是右侧排序正确区间的最小值,也要放在搜索范围里;

当找不到递增序列时,取两个数的最小值;

class Solution(object):def findMin(self, nums):""":type nums: List[int]:rtype: int"""left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[left] < nums[mid] and nums[mid] < nums[right]:return nums[left]elif nums[left] < nums[mid] and nums[mid] > nums[right]:    # [left, mid]排序正确left = mid + 1      elif nums[left] > nums[mid] and nums[mid] < nums[right]:  # [mid, right]排序正确right = mid else:return min(nums[left], nums[right])
4 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

方法一:合并两个有序数组后取中间位置的元素;                     时间复杂度O(m+n) 空间复杂度O(m+n)

将问题转换为两个有序数组中取第k小的数    k=(m+n)/2 or (m+n)/2+1

方法二:使用双指针,每次移动较小值的指针至移动k次;         时间复杂度O(m+n) 空间复杂度O(1)

方法三: 比较nums1[k/2-1]和nums2[k/2-1],对于二者中的较小值(假设nums1[k/2-1]),其在合并数组中的下标一定小于(k/2-1)*2+1<k,就不可能是目标值,此时nums1[0:k/2]也不可能含有目标值;随后根据排除掉的长度更新k后继续循环;

终止条件:某个数组为[ ],直接返回另一个数组的第k个元素;

                  k=1,直接取两数组第一个元素的最小值;

class Solution(object):def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""def getKthElement(k):index1, index2 = 0, 0while True:# 特殊情况if index1 == m:return nums2[index2 + k - 1]if index2 == n:return nums1[index1 + k - 1]if k == 1:return min(nums1[index1], nums2[index2])# 正常情况newIndex1 = min(index1 + k // 2 - 1, m - 1)        # 防止越界newIndex2 = min(index2 + k // 2 - 1, n - 1)pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]if pivot1 <= pivot2:k -= newIndex1 - index1 + 1index1 = newIndex1 + 1else:k -= newIndex2 - index2 + 1index2 = newIndex2 + 1m, n = len(nums1), len(nums2)totalLength = m + nif totalLength % 2 == 1:return getKthElement((totalLength + 1) // 2)else:return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2.

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

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

相关文章

Flink CDC 同步数据到Doris

Flink CDC 同步数据到Doris Flink CDC 是基于数据库日志 CDC(Change Data Capture)技术的实时数据集成框架,支持了全增量一体化、无锁读取、并行读取、表结构变更自动同步、分布式架构等高级特性。配合 Flink 优秀的管道能力和丰富的上下游生态,Flink CDC 可以高效实现海量…

【现代企业管理】企业组织结构和组织文化的理论与实践——以华为为例

一、前言 管理是科学和艺术的统一体&#xff0c;它是企业成长的保证。企业管理中&#xff0c;管理者面对的往往不是一个完整的系统&#xff0c;而是各种不具有整体规律性的零碎信息的总和&#xff0c;因此进行信息的整合和研究是管理的重点和关键。 组织管理作为管理的四大职…

OWASP API 安全风险,有哪些安全措施

随着互联网的快速发展&#xff0c;Web应用已成为人们日常生活和工作中不可或缺的一部分。然而&#xff0c;Web应用的安全问题也日益凸显&#xff0c;给企业和个人带来了极大的风险。 对于一些安全行业的用户来说&#xff0c;不少都听过关于OWASP这个词&#xff0c;很多用户想要…

设计模式12--组合模式

定义 案例一 案例二 优缺点

【Redis】Redis 生产问题。如何确保缓存和数据库数据的一致性? 常见的缓存更新策略?

目录 缓存穿透 缓存穿透解决办法 缓存击穿 击穿解决办法&#xff1f; 缓存穿透和缓存击穿的区别&#xff1f; 缓存雪崩 雪崩解决办法&#xff1f; 如何确保缓存和数据库数据的一致性&#xff1f; 常见的缓存更新策略&#xff1f; 缓存穿透 定义&#xff1a;缓存穿透说…

Linux学习笔记————C 语言版 LED 灯实验

这里写目录标题 一、实验程序编写二、 汇编部分实验程序编写三、C 语言部分实验程序编写四、编译下载验证 汇编 LED 灯实验中&#xff0c;我们讲解了如何使用汇编来编写 LED 灯驱动&#xff0c;实际工作中是很少用到汇编去写嵌入式驱动的&#xff0c;毕竟汇编太难&#xff0c;而…

linux设置Nacos自启动

前提&#xff1a;已经安装好nacos应用 可参考&#xff1a;Nacos单机版安装-CSDN博客 1. 创建nacos.service 1.1 在 /lib/systemd/system 目录底下&#xff0c;新建nacos.service文件 [Unit] Descriptionnacos Afternetwork.target[Service]Typeforking# 单机启动方式&#…

OmniGraffle Pro for mac 出色的图形设计软件

OmniGraffle Pro是一款非常出色的图形设计软件&#xff0c;它主要适用于Mac和iPad平台&#xff0c;可以用来轻松绘制各种精美的图表、示意图和界面设计。 软件下载&#xff1a;OmniGraffle Pro for mac中文注册激活版 以下是OmniGraffle Pro的一些主要特点和功能&#xff1a; 界…

Java就近原则和this关键字

Java 中的就近原则和 this 关键字有着密切的关系&#xff0c;特别是在处理成员变量与方法参数同名的情况下。就近原则指的是在同一作用域下&#xff0c;优先使用最近声明的变量或参数。 在 Java 中&#xff0c;如果一个方法的参数与类的成员变量同名&#xff0c;为了明确指示要…

HTX Ventures:为什么BounceBit可能成为新的BTC生态解决方案?

随着BTC现货ETF的通过&#xff0c;全球各大机构和个人都在不断加码对BTC的持仓&#xff0c;BTC价格也随之上升&#xff0c;目前已上升至全球市值排名前十的资产。在本轮市场周期中&#xff0c;BTC铭文和BTC扩容是两个被市场高度关注的细分赛道。BTC生态资产的多元化收益探索正在…

HAL STM32 硬件I2C方式读取AS5600磁编码器获取角度例程

HAL STM32 硬件I2C方式读取AS5600磁编码器获取角度例程 &#x1f4cd;相关篇《STM32 软件I2C方式读取AS5600磁编码器获取角度例程》 ✨stm32使用硬件I2C去读取角度数据&#xff0c;通过STM32CubeMX工具配置工程&#xff0c;读取角度数据&#xff0c;只需要调用一个函数&#xf…

如何使用VNC+Cpolar实现Windows电脑公网远程控制Ubuntu系统桌面

文章目录 前言1. VisualSVN安装与配置2. VisualSVN Server管理界面配置3. 安装cpolar内网穿透3.1 注册账号3.2 下载cpolar客户端3.3 登录cpolar web ui管理界面3.4 创建公网地址 4. 固定公网地址访问 前言 SVN 是 subversion 的缩写&#xff0c;是一个开放源代码的版本控制系统…

复变函数导数求解(包含矢量、矩阵形式)

文章目录 目录 文章目录 前言 一、复变函数导数 1.1 导数定义 1.2 求导法则 1.3 存在条件 二、常用求导结论 2.1 标量函数对标量的导数 2.2 标量函数对矢量的导数 2.3 标量函数对矩阵的导数 总结 前言 本文将从信号处理的角度简单阐明复变函数理论的重要性&#xff…

Ansys Zemax | 如何将光栅数据从Lumerical导入至OpticStudio(上)

附件下载 联系工作人员获取附件 本文介绍了一种使用Ansys Zemax OpticStudio和Lumerical RCWA在整个光学系统中精确仿真1D/2D光栅的静态工作流程。将首先简要介绍方法。然后解释有关如何建立系统的详细信息。 本篇内容将分为上下两部分&#xff0c;上部将首先简要介绍方法工…

工业边缘计算网关在工业中的应用以及其为工业生产带来的效益-天拓四方

随着信息技术的不断发展&#xff0c;工业领域对数据处理和分析的需求日益增长。工业边缘计算网关作为一种新型技术&#xff0c;正逐渐成为工业数字化转型的关键驱动力。本文将通过一个具体案例阐述工业边缘计算网关在工业中的应用&#xff0c;以及其为工业生产带来的显著效益。…

Stable Diffusion 模型下载:epiCPhotoGasm(真实、照片)

本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里,订阅后可阅读专栏内所有文章。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八下载地址模型介绍

【QT入门】 QListWidget各种常见用法详解之列表模式

往期回顾 【QT入门】 Qt代码创建布局之setLayout使用-CSDN博客 【QT入门】 Qt代码创建布局之多重布局变换与布局删除技巧-CSDN博客 【QT入门】 QTabWidget各种常见用法详解-CSDN博客 【QT入门】 QListWidget各种常见用法详解之列表模式 QListWidget有列表和图标两种显示模式&a…

基于ssm汽车养护管理系统论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本汽车养护管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…

啥是MCU,MCU科普

啥是MCU&#xff0c;MCU科普 附赠自动驾驶学习资料和量产经验&#xff1a;链接 MCU是Microcontroller Unit 的简称&#xff0c;中文叫微控制器&#xff0c;俗称单片机&#xff0c;是把CPU的频率与规格做适当缩减&#xff0c;并将内存、计数器、USB、A/D转换、UART、PLC、DMA等…

YARN集群 和 MapReduce 原理及应用

YARN集群模式 本文内容需要基于 Hadoop 集群搭建完成的基础上来实现 如果没有搭建&#xff0c;请先按上一篇: <Linux 系统 CentOS7 上搭建 Hadoop HDFS集群详细步骤> 搭建&#xff1a;https://mp.weixin.qq.com/s/zPYsUexHKsdFax2XeyRdnA 配置hadoop安装目录下的 etc…