首页 > 其他分享 >LeetCode 81.搜索旋转排序数组II

LeetCode 81.搜索旋转排序数组II

时间:2022-11-25 11:33:40浏览次数:71  
标签:中点值 nums 边界值 II 目标值 边界 81 LeetCode target

LeetCode 81.搜索旋转排序数组II题目链接:

​https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/​


题目描述:

已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= 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. 1 <= nums.length <= 5000

2. -104 <= nums[i] <= 104

3. 题目数据保证 nums 在预先未知的某个下标上进行了旋转

4. -104 <= target <= 104


题目分析:

这道题我们可以直接使用暴力法,遍历数组,如果有元素与目标值相同,则返回true,否则返回false(见题解一)。我们也可以使用二分查找法,我们先定义左右边界,左边界初始化为数组头,右边界初始化为数组尾,当左边界小于等于右边界时执行循环,获取当前区间中点值,如果中点值刚好等于目标值,说明查找到目标值,返回true。如果左边界值等于中点值,无法判断哪个区间是递增的,我们可以微调区间,左边界向右移动一位,再进行下一轮判断。如果中点值小于等于右边界值,说明右区间递增,同时,如果目标值大于中点值且目标值小于等于右边界值,左边界更新至中点右一个元素;否则目标值小于中点值,右边界更新至中点左一个元素。如果中点值大于左边界值,说明左区间递增,同时,如果目标值大于等于左边界值且目标值小于中点值,右边界更新至中点左一个元素;否则左边界更新至中点右一个元素。如果遍历完还没有找到目标值,返回false。


题解一(暴力法):

执行用时: 1 ms

内存消耗: 37.6 MB

class Solution {
public boolean search(int[] nums, int target) {
// 获取数组中元素的值
for (int x : nums)
// 如果数组中有一个元素值刚好与目标值相等
if (x == target)
// 返回true
return true;
// 数组中找不到目标元素,返回false
return false;
}
}


题解二(二分查找法):

执行用时: 1 ms

内存消耗: 37.7 MB

class Solution {
public boolean search(int[] nums, int target) {
// 定义左右边界
int left = 0, right = nums.length - 1;
// 当左边界小于等于右边界时执行循环
while (left <= right) {
// 获取区间中点值
int mid = (left + right) / 2;
// 如果中点值刚好等于目标值,说明查找到目标值,返回true
if (nums[mid] == target)
return true;
// 如果左边界值等于中点值,无法判断哪个区间是递增的
if (nums[left] == nums[mid])
// 移动左边界
++left;
// 如果中点值小于等于右边界值,说明右区间递增
else if (nums[mid] <= nums[right])
// 如果目标值大于中点值且目标值小于等于右边界值
if (target > nums[mid] && target <= nums[right])
// 左边界更新至中点右一个元素
left = mid + 1;
// 否则目标值小于中点值
else
// 右边界更新至中点左一个元素
right = mid - 1;
// 如果中点值大于左边界值,说明左区间递增
else
// 如果目标值大于等于左边界值且目标值小于中点值
if (target >= nums[left] && target < nums[mid])
// 右边界更新至中点左一个元素
right = mid - 1;
else
// 左边界更新至中点右一个元素
left = mid + 1;
}
// 没有找到目标值,返回false
return false;
}
}


题目来源:力扣(LeetCode)


标签:中点值,nums,边界值,II,目标值,边界,81,LeetCode,target
From: https://blog.51cto.com/u_15891283/5886071

相关文章

  • LeetCode 34.在排序数组中查找元素的第一个和最后一个位置
    LeetCode34.在排序数组中查找元素的第一个和最后一个位置题目链接:​​https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/​​......
  • Linux下vim增加ascii流程图绘制功能试验
    简单用法(在英文输入模式下)开启:DIstart关闭:DIstop空格按一下启动绘制,空格再按一下启动擦出功能当绘制时,上下左右自动直线和转折。  剪头向上shift+6、箭头下v 、......
  • LeetCode 76.最小覆盖子串
    LeetCode76.最小覆盖子串题目链接:​​https://leetcode-cn.com/problems/minimum-window-substring/​​题目描述:给你一个字符串 s 、一个字符串 t 。返回 s 中涵......
  • 硬件知识--IIC协议
    IIC协议IIC通信只有两条线就可以实现,一条是时钟线SCL,另一条是数据线SDA。是一种半双工通信协议。关于IIC协议主要记住以下几点:1、数据线SDA只有在时钟线SCL为低电平的时......
  • IIC时序图
    IIC(Inter-IntegratedCircuit)总线是一种由PHILIPS公司在80年代开发的两线式串行总线,用于连接微控制器及其外围设备。它是半双工通信方式。IIC串行总线一般有两根信号线,一根......
  • leetcode 104. 二叉树的最大深度 js实现
    给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例:给定二叉树 [3,9,20,null,null......
  • leetcode 344. 反转字符串 js实现
    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用O(1)的额外空间解......
  • leetcode 21. 合并两个有序链表 js实现
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示......
  • leetcode_Day2_35搜索插入位置
    1.题目  2.解一 主要思路:二分法,不多赘述,为题目所给标准解法。3.解二   主要思路:循环对比,自己想的,感觉写的非常冗余,内存占用和速度都很大。不过没学过算法,......
  • leetcode 19. 删除链表的倒数第 N 个结点 js实现
    给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。示例1:输入:head=[1,2,3,4,5],n=2输出:[1,2,3,5]示例2:输入:head=[1],n=1输出:[]示例3:......