在数组中查找峰元素

在数组中查找峰元素

如果您想练习数据结构和算法程序,可以通过 100多种数据结构和算法程序.

在本文中,我们将看到如何在阵列中找到峰元素。


问题

给定一个整数数组。在数组中找到峰值元素。
Peak Element 是元素 数组 这是 GREATER THAN / EQUAL TO its neighbours, that is, for an element at i th index, the neighbour elements at index i-1 & i+1 must be greater than equal to element at i th position.
现在

一个数组可以有几个峰值元素,我们需要输出其中的任何一个。


解决此问题的基本方法是遍历整个数组以及每个数组 i th element check the condition rr[i-1] = arr[i+1].

  • 对于数量相等的数组,每个元素都是峰值元素。
  • 对于拐角元素,条件会稍作调整,因为它们只有一个邻居,也就是说,
    对于 extreme left element we just need to check if rr[i+1] <= arr[i].
    对于 extreme right element we just need to check rr[i-1] <= arr[i].
  • The worst time complexity of this approach would be O(n).

    高效方法:

    我们可以对它使用分而治之的方法,该方法使用类似于二进制搜索的算法,其中条件用中间元素检查,并根据结果在初始数组的一半中搜索答案。随着每次调用的元素数量减少一半,这将带来最差的时间复杂度, O(log(n)).

    算法 :
    如果数组的中间元素大于或等于其邻居,则将其与数组的中间元素进行比较。如果中间元素大于或等于其邻居,则将其返回。
    如果元素小于其左邻元素,则可以确保峰值元素位于左元素中。

    为什么?

    考虑一个数组,

                                          整型[] arr = {a1, a2, a3, a4, a5, a6, a7};
    There arise 2 cases when left neighbour(a3) is greater than middle element(a4) i.e. a3 > a4:
    Case-1 : if the left neighbour(a3) is corner, then this is our peak element.
    Case-2 :如果left元素不是corner元素。这里又出现了两种可能性,即

    1. 如果 a2 > a3 , then this becomes the same recursive subproblem which we discussed
      以上及其结果将最终递归计算。
    2. 如果 a2 < a3, then again a3 is our peak element because, a3 > a2  &  a3 > a4, i.e. a3 is greater than or equal to its neighbours.

    当右邻居(a5)大于中间元素时,遵循相同的过程。

    当您在程序上方运行时,将得到以下输出。

    4 10 20 40 15
    rr []:{10 20 40 15}
    峰值元素是:在索引2处找到40

    那’关于如何在数组中查找峰元素的所有内容。
    如有任何疑问或编辑,请发表评论。快乐学习🙂


    导入联系人

    您可能还喜欢:

相关文章

  • 3月28日

    对0、1和2的数组进行排序

    如果您想练习数据结构和算法程序,可以阅读100多种数据结构和算法程序。在这篇文章中,我们将看到如何对0、1和2s的数组进行排序。我们已经看到了有关对数组中的0s和1s进行排序的文章。问题给定一个包含零的数组,[…]

  • 3月04

    通过跳转检查是否有可能到达给定数组的末尾

    如果您想练习数据结构和算法程序,可以阅读100多种数据结构和算法程序。问题给定一个具有正整数作为元素的数组,该数组指示可以从数组中任何位置进行跳转的最大长度。检查是否可以[…]

  • 2月17日

    检查数组元素是否连续

    如果您想练习数据结构和算法程序,可以阅读100多种数据结构和算法程序。在这篇文章中,我们将看到如何检查数组元素是否连续。问题给定一个数组,我们需要检查数组是否包含连续的元素。例如:输入:array [] = {5,3,4,[…]

  • 11月1日

    在数组中找到局部最小值

    如果您想练习数据结构和算法程序,可以阅读100多种数据结构和算法程序。在这篇文章中,我们将看到如何在数组中找到局部最小值。问题如果一个元素小于其相邻元素,则它是局部最小值。 int [] arr = {10,5,3,[…]

  • 10月22日

    爪哇中的滑动窗口最大值

    在这篇文章中,我们将看到有关Java问题中滑动窗口最大值的问题给定一个整数数组和一个整数k,请从所有大小为K的连续子数组中找到max的元素。例如:Input:int [] arr = {2 ,6,-1,2,4,1,-6,5} int k = 3输出:[[]的每个子数组分别为6,6,4,4,4,5,5…]

  • 10月20日

    计算排序数组中每个元素的出现次数(或频率)

    如果您想练习数据结构和算法程序,可以阅读100多种数据结构和算法程序。在这篇文章中,我们将看到如何计算已排序数组中每个元素的出现次数(或出现频率)问题给定一个包含重复项的整数排序数组。找出每个[…]

发表评论

您的电子邮件地址不会被公开。 必需的地方已做标记 *

订阅我们的新闻

获取质量教程到您的收件箱。现在订阅。