在数组中查找峰元素

如果您想练习数据结构和算法程序，可以通过 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）大于中间元素时，遵循相同的过程。

PeakElement.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

包 组织.Arpit.爪哇2blog;   进口 爪哇.实用程序.扫描器;   上市 类 PeakElement {       上市 静态的 虚空 主要(串[] args) {           扫描器 scn = 新 扫描器(系统.在);         整型[] rr = 新 整型[scn.nextInt()];           对于 (整型 i = 0; i < rr.长度; i++) {             rr[i] = scn.nextInt();         }           整型 peakIndex = 解决(0, rr.长度 - 1, rr);           系统.出.打印(“ arr []：{”);         对于 (整型 i = 0; i < rr.长度; i++) {             系统.出.打印(”+rr[i]);         }           系统.出.打印(“}”);         系统.出.打印(“峰值元素是：” + rr[peakIndex] +                                    “在索引处找到” + peakIndex);       }       上市 静态的 整型 解决(整型 开始, 整型 结束, 整型[] rr) {           //找到将数组分为两部分的中间         整型 中 = (开始 + 结束) / 2;           //如果mid元素不是corner元素并且更大                 //等于或等于其邻居         如果 ((中 > 0 && 中 < rr.长度 - 1) && (rr[中] >=                      rr[中 + 1] && rr[中] >= rr[中 - 1])) {             返回 中;         }           //如果mid元素是left corner元素并且更大                   //大于或等于它的右邻。           其他 如果 (中 == 0 && 中！= rr.长度-1 && rr[中] >=                          rr[中 + 1])         {             返回 中;         }           //如果mid元素是右上角的元素并且更大                 //等于或等于它的左邻居。           其他 如果 (中 == rr.长度 - 1 && 中！= 0 &&                          rr[中 - 1] <= rr[中])         {             返回 中;         }           //如果mid元素小于其左邻居，                 //然后，峰值元素肯定会在左侧。           其他 如果 (中 ！= 0 && rr[中 - 1] > rr[中])         {             返回 解决(开始, 中 - 1, rr);         }         其他         {             如果(中 + 1 <= rr.长度-1)             {                返回 解决(中 + 1, 结束, rr);             }         }         //如果数组只有一个元素，则                 //峰值元素         返回 0;     }   }

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

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

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



导入联系人
您可能还喜欢：
对0、1和2的数组进行排序
通过跳转检查是否有可能到达给定数组的末尾
检查数组元素是否连续
在数组中找到局部最小值
爪哇中的滑动窗口最大值
计算排序数组中每个元素的出现次数（或频率）
在数组中查找具有给定总和的子数组。
数1’s在已排序的二进制数组中
在整数数组中查找第一个重复元素
打印给定数组的所有子数组
• 1
• 2
• 3
• 4
• ›