在C中的数组元素高峰 [英] Peak element in an array in c

问题描述

我给整型数组。我在这找到一个峰值元素。
数组元素是高峰期，如果它是不会小比它的邻居。
对于角落的元素，只考虑一个邻居。

I am given an array of integers. I have to find a peak element in it. An array element is peak if it is NOT smaller than its neighbors. For corner elements,consider only one neighbor.

例如：

有关输入数组 {10，20，15，2，23，90，67}
有两个高峰元素：20和90我需要返回任何一个峰元素

For input array {10, 20, 15, 2, 23, 90, 67} there are two peak elements: 20 and 90. I need to return any one peak element.

我试图解决的办法是阵列的线性扫描，我发现了一个高峰元素。这种方法的最坏情况下的时间复杂度是O（N）。

The solution i tried is a linear scan of array and i found a peak element. The worst case time complexity of this method would be O(n).

我们可以找到最糟糕的时间复杂度为O（N）？

Can we find the peak element in worst time complexity better than O(n)?

推荐答案

是的，你可以做到在O（log n）的使用类似于二进制搜索的想法。指向矢量的中间，检查它的邻居。如果是大于邻国都，然后返回元素，它是一个高峰。如果右元素为大，则在该阵列的右侧递归找到的峰值。如果左侧元件越大，则递归地发现在阵列左侧的峰

Yes, you can do it in O(log n) using an idea similar to binary search. Point to the middle of the vector and check its neighbours. If it is greater than both of its neighbours, then return the element, it is a peak. If the right element is greater, then find the peak recursively in the right side of the array. If the left element is greater, then find the peak recursively in the left side of the array.

这篇关于在C中的数组元素高峰的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！