[路飞]_leetcode-81-搜索旋转排序数组 II

简介: leetcode-81-搜索旋转排序数组 II

网络异常,图片无法展示
|


「这是我参与2022首次更文挑战的第28天,活动详情查看:2022首次更文挑战


[题目地址][B站地址]


已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]


给你 旋转后 的数组 nums 和一个整数 target ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ,则返回 true ,否则返回 false


你必须尽可能减少整个操作步骤。


示例 1:


输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
复制代码


示例 2:


输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
复制代码


提示:


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


进阶:


  • 这是 搜索旋转排序数组 的延伸题目,本题中的 nums  可能包含重复元素。
  • 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?


解题思路


本题最简单的办法就是一趟从头到尾的扫描,如果过程中发现某个元素等于目标值

target,则返回 true,否则返回 false


当然还有一个取巧的办法,利用数组的 indexOf() 方法判断 nums.indexOf(target) 是否等于 -1


接下来我们讲另外一种思路:


根据题意,输入数组 nums 是一个升序的数组,只不过在某个下标 k 处进行了翻转,导致前半部分和后半部分分别有序,而且前半部分大于后半部分。


而如果 target 小于此时的 nums[0] 的话,则如果 target 存在,肯定在后半部分,我们只需要在后半部分找。


反之,则如果 target 存在,肯定在前半部分,我们只需要在前半部分找。


代码实现


var search = function (nums, target) {
  // 如果 target 比第一个数字小,则如果存在,会在后半部分
  if (nums[0] > target) {
    for (let i = nums.length - 1; i >= 0; i--) {
      if (nums[i] === target) return true
      // 如果到了前半部分或者下标0位置还没找到,则一定不存在,返回 false
      if ((i > 0 && nums[i - 1] > nums[i]) || i === 0) return false
    }
  } else {
    // 如果 target 大于等于第一个数字,则如果存在,会在前半部分
    for (let i = 0; i < nums.length; i++) {
      if (nums[i] === target) return true
      // 如果到了后半部分或者数组末尾还没找到,则一定不存在,返回 false
      if ((i < nums.length - 1 && nums[i] > nums[i + 1]) || i === nums.length - 1) return false
    }
  }
}
复制代码


至此我们就完成了 leetcode-81-搜索旋转排序数组 II


如有任何问题或建议,欢迎留言讨论!👏🏻👏🏻👏🏻

相关文章
|
2月前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
17 2
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
26 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
21 0
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
76 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
64 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
128 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
50 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
4月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
76 7