首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何在数组中找到第一个峰值后的第一个最小值?

在数组中找到第一个峰值后的第一个最小值,可以通过以下步骤实现:

  1. 首先,定义一个函数来找到数组中的峰值。峰值是指数组中的一个元素,它大于其相邻的两个元素。可以使用二分查找的方法来实现,具体步骤如下:
    • 初始化左指针left为0,右指针right为数组长度减1。
    • 进入循环,直到左指针大于等于右指针:
      • 计算中间指针mid,即mid = (left + right) / 2。
      • 如果mid处于上升趋势,即nums[mid] < nums[mid+1],则峰值必然在mid的右侧,更新左指针left为mid+1。
      • 否则,峰值必然在mid的左侧或就是mid本身,更新右指针right为mid。
    • 返回left作为峰值的索引。
  • 找到峰值后,可以使用线性搜索来找到峰值后的第一个最小值。具体步骤如下:
    • 从峰值的索引开始,遍历数组的右侧元素。
    • 如果当前元素小于前一个元素,则找到了第一个最小值,返回该元素。
    • 如果遍历结束仍未找到最小值,则说明数组是递增的,返回数组的最后一个元素作为最小值。

下面是一个示例的JavaScript代码实现:

代码语言:txt
复制
function findPeakAndMin(nums) {
  // 找到峰值
  function findPeak(nums, left, right) {
    while (left < right) {
      let mid = Math.floor((left + right) / 2);
      if (nums[mid] < nums[mid + 1]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    return left;
  }

  let peakIndex = findPeak(nums, 0, nums.length - 1);

  // 找到峰值后的第一个最小值
  for (let i = peakIndex; i < nums.length - 1; i++) {
    if (nums[i] > nums[i + 1]) {
      return nums[i + 1];
    }
  }

  // 数组是递增的,返回最后一个元素作为最小值
  return nums[nums.length - 1];
}

// 示例用法
let nums = [1, 3, 5, 2, 4, 6, 8];
let min = findPeakAndMin(nums);
console.log("第一个峰值后的第一个最小值为:" + min);

这段代码中,我们首先通过二分查找找到数组中的峰值,然后从峰值的索引开始遍历数组,找到第一个最小值并返回。如果数组是递增的,则返回数组的最后一个元素作为最小值。

请注意,以上代码仅为示例,实际应用中可能需要根据具体情况进行适当的修改和优化。

关于云计算、IT互联网领域的名词词汇,可以参考腾讯云的官方文档和产品介绍页面,其中包含了丰富的云计算相关知识和产品信息。具体链接地址请参考腾讯云官方网站。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

数组特性妙用!如何找到「缺失第一个正数」

作者 | P.yh 今天分享题目来源于 LeetCode 第 41 号问题:缺失第一个正数。题目难度为 Hard。本文使用了一个比较 Trick 解法。...题目描述 给定一个未排序整数数组,找出其中没有出现最小正整数。...数组应该是属于一类最最基础数据结构,除去 length 之外,就只有两个属性 index 和 value,那这道题就变成了 如何利用数组 value 和 index 之间关系来找到最小缺失正整数...index 和 value 关系,我们可以通过 index 来判定整数存在性 第一点很好理解,一个数组总共有 array.length 这么多个数,全部排满,也就是 1,2,…array.length...第一点,交换完,需要判断交换过来数是否需要被放到相应地方,例如 [2,3,1] 第二点,元素越界的话,以及元素 value 已经和 index 对应上了,那么就应该继续遍历,例如 [0,-1,1]

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

    前言: 这是一道给很经典二分查找题目,并且该二分查找算法不同于简单二分,是二分查找进阶版本。 一、题目描述 34....排序数组中查找元素第一个和最后一个位置 给你一个按照非递减顺序排列整数数组 nums,和一个目标值 target。请你找出给定目标值在数组开始位置和结束位置。...如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 算法解决此问题。...就是当 x >= t 时,right = mid,而不是mid - 1,这是因为我们最开始是将数组分为两个部分,一部分就是大于等于该元素,如果right = mid - 1,又可能会将我们要求数据筛掉...int right = nums.size() - 1; int mid = 0; int begin = 0; while(left < right)//第一个小细节

    10010

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

    排序数组中查找元素第一个和最后一个位置 给定一个按照升序排列整数数组 nums,和一个目标值 target。找出给定目标值在数组开始位置和结束位置。...寻找target在数组左右边界,有如下三种情况: 情况一:target 在数组范围右边或者左边,例如数组{3, 4, 5},target为2或者数组{3, 4, 5},target为6,此时应该返回...nums 数组中二分查找得到第一个大于等于 target下标(左边界)与第一个大于target下标(右边界); # 2、如果左边界<= 右边界,则返回 [左边界, 右边界]。...target下标 ,否则找到第一个大于target下标 if nums[middle] > target or (lower and nums[middle] >=...nums 数组中二分查找得到第一个大于等于 target下标leftBorder; # 2、 nums 数组中二分查找得到第一个大于等于 target+1下标, 减1则得到rightBorder;

    4.7K20

    LeetCode-34-排序数组中查找元素第一个和最后一个位置

    # LeetCode-34-排序数组中查找元素第一个和最后一个位置 给定一个按照升序排列整数数组 nums,和一个目标值 target。找出给定目标值在数组开始位置和结束位置。...你算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值,返回 [-1, -1]。...0时,直接返回[-1,1] 当数组长度为1时,判断第一个数字是否等于target,等于则返回[0,0],否则返回[-1,-1] 初始化头尾指针 移动头指针,直到找到第一个等于target位置,如果找完了都没有找到...end,end] 反之,返回头尾指针区间[start,end] 方法2、二分查找(fast): 通过判断mid位置数值,决定左右边界移动 当nums[mid]<target时,说明targetmid...,这时候只需要查找另外一个边界等于target即可,可以进行循环移动查找,最后返回[start,end]即可 如果没有找到,返回[-1,-1] 方法3、递归分治(low): 通过二分查找切分数组寻找左右子数组

    2.2K20

    LeetCode题目34:排序数组中查找元素第一个和最后一个位置

    原题描述 + 给定一个按照升序排列整数数组 nums,和一个目标值 target。找出给定目标值在数组开始位置和结束位置。 你算法时间复杂度必须是 O(log n) 级别。...如果数组中不存在目标值,返回 [-1, -1]。...普通二分查找找到target立即返回,所以我们需要做变式,情况分为以下两种。 寻找左边界 还是得举个例子。...因为lower左边不是target,而higher也一直尽可能往左挪动。 寻找右边界 与上面过程相反,我们尽可能向右挪动lower,让其与higher相撞即可。...但如果复用上面的逻辑,每次挪动时令lower=mid+1,那么最终lower一定会与higher相撞于最后一个target一个位置。此时lower-1才是所求。

    3.1K20

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

    前言 今天主要讲解内容是:如何在已排序数组中查找元素第一个和最后一个位置。以 leetcode 34 题作为例题,提供二分查找解题思路,供大家参考。...,所以可以通过二分查找方法来解答此题; 如何查找元素第一个位置?...1),不断向 mid 左侧收缩,最后达到锁定左边界(元素第一个位置)目的; 如何查找元素最后一个位置?...同查找元素第一个位置类似,查找到数组中某元素值等于目标值 target 时,不立即返回,通过增大查找区间下边界 low (令 low = mid + 1),不断向 mid 右侧收缩,最后达到锁定右边界...继续缩小查找区间上边界 high。 ? end: 由于此时 high < low,代表查找 8 在数组中出现第一个位置结束。

    2.6K20

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

    一、题目描述 给定一个按照升序排列整数数组 nums,和一个目标值 target。找出给定目标值在数组开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。...-109 <= target <= 109 二、解题思路 使用二分法查找第一个位置,初始化两个变量low=0,hight=nums.length-1 1、当low>high时,表示没有找到,返回-1...nums[mid]时,说明目标值左侧,往左侧递归查找,否则往右侧递归查找 查找最后一个位置同理,唯一不同是第4、5步 4、假如nums[mid]等于target且nums[mid]比相邻右侧元素小...,返回下标mid ​5、当目标值大于等于nums[mid]时,说明目标值右侧,往右侧递归查找,否则往左侧递归查找 三、代码 package search_range; public class Solution...rs.length;i++){ System.out.println(rs[i]); } } } 四、复杂度分析 时间复杂度: O(logn) ,其中 n 为数组长度

    1.9K10

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

    前言 今天刷题目是:排序数组中查找元素第一个和最后一个位置,这道题目最开始AC以后,然后做了两步优化操作,供大家参考。...题目 leetcode-34:排序数组中查找元素第一个和最后一个位置 分类(tag):二分查找这一类 英文链接:https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array...找出给定目标值在数组开始位置和结束位置。 你算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值,返回 [-1, -1]。...4,这个下标是可能最左4下标所以要记录保存一下; 观察这个数组,可以知道,最左4下标是2,所以为了找到这个最左下标,需要令right值去等于mid-1;这样就把right这一边慢慢地往左靠...-1,如果不是-1,那说明需要继续找最右边下标,如果是-1的话,那么说明数组中没有target值,所以我们也不必去找最右边下标了,因为已经找过了,不存在,还费这事干嘛,最终这样优化完速度快了1ms

    2.6K30

    排序数组中查找元素第一个和最后一个位置(leetcode34)

    给定一个按照升序排列整数数组 nums,和一个目标值 target。找出给定目标值在数组开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。...示例 1: 输入:nums = [5,7,7,8,8,10], target = 8 输出:[3,4] 解析: 方法一:二分查找 二分查找中,寻找leftIdx 即为在数组中寻找第一个大于等于 target...下标,寻找 rightIdx 即为在数组中寻找第一个大于target 下标,然后将下标减一。...两者判断条件不同,为了代码复用,我们定义 binarySearch(nums, target, lower) 表示 nums 数组中二分查找 target 位置,如果 lower 为 true,...则查找第一个大于等于 target 下标,否则查找第一个大于target 下标。

    1.8K10

    排序数组中查找元素第一个和最后一个位置--题解

    排序数组中查找元素第一个和最后一个位置 给定一个按照升序排列整数数组 nums,和一个目标值 target。找出给定目标值在数组开始位置和结束位置。...如果数组中不存在目标值 target,返回 [-1, -1]。 进阶: 你可以设计并实现时间复杂度为 O(log n) 算法解决此问题吗?...: 输入:nums = [], target = 0 输出:[-1,-1] 提示: 0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 是一个非递减数组...mid - 1 } else if nums[mid] == target { end = mid } else { start = mid + 1 } } //此处防止数组第一个数是...target int) int { start, end := 0, len(nums)-1 for start < end { //此处注意,为了防止 start=mid<end 导致死循环问题

    1.9K30

    LeetCode - #34 排序数组中查找元素第一个和最后一个位置(Top 100)

    微博:@故胤道长[1]**) Swift 算法题题解整理为文字版以方便大家学习与阅读。...如果大家有建议和意见欢迎文末留言,我们会尽力满足大家需求。 难度水平:中等 1. 描述 给定一个按照升序排列整数数组 nums,和一个目标值 target。...找出给定目标值在数组开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 进阶: 你可以设计并实现时间复杂度为 O(log n) 算法解决此问题吗? 2....nums = [], target = 0 输出:[-1,-1] 约束条件: 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 nums 是一个非递减数组...时间复杂度: O(logn) 空间复杂度: O(1) 该算法题解仓库:LeetCode-Swift[2] 点击前往 LeetCode[3] 练习 特别感谢 Swift社区 编辑部每一位编辑,感谢大家辛苦付出

    1.5K20

    ​LeetCode刷题实战34:排序数组中查找元素第一个和最后一个位置

    今天和大家聊问题叫做在排序数组中查找元素第一个和最后一个位置,我们先来看题面: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array...题意 给定一个按照升序排列整数数组 nums,和一个目标值 target。找出给定目标值在数组开始位置和结束位置。 你算法时间复杂度必须是 O(log n) 级别。...如果数组中不存在目标值,返回 [-1, -1]。...版本2:是指二分法执行完毕,返回target最左边位置,求出另一个边界! 关于详细说明,请看这篇[二分搜索](二分查找有几种写法?它们区别是什么?...bisect库 简要介绍一下, bisect.bisect_left(a,x,lo=0,hi=len(a))a中找x最左边数索引,如果找不到就返回插入索引. bisect.bisect(a, x,

    1.2K20

    打卡群刷题总结0630——排序数组中查找元素第一个和最后一个位置

    排序数组中查找元素第一个和最后一个位置 链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array...给定一个按照升序排列整数数组 nums,和一个目标值 target。...找出给定目标值在数组开始位置和结束位置。 你算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值,返回 [-1, -1]。...那么来了,对于二分查找变形体,直接用模板就行了: 1)查找第一个等于target数,我们使得循环结束nums[r] < target <= nums[l],那么第一个红框填<,第二个红框填l(一定存在解前提...); 2)查找第一个大于target数,我们使得循环结束nums[r] <= target < nums[l],那么第一个红框填<=,第二个红框填l; 3)查找最后一个小于target数,我们使得循环结束

    68910
    领券