c中数组中的峰值元素

Question

我得到了一个整数数组.我必须在其中找到一个峰值元素.如果数组元素不小于其邻居,则它是峰值.对于角落元素,仅考虑一个邻居.

例如:

对于输入数组{10, 20, 15, 2, 23, 90, 67} ,有两个峰值元素:20和90.我需要返回任何一个峰值元素.

我尝试的解决方案是阵列的线性扫描,我发现了一个峰值元素.该方法的最坏情况时间复杂度为O(n).

我们能否在最差时间复杂度中找到比O(n)更好的峰值元素？

Answer 1

是的,您可以使用类似于二进制搜索的想法在O(log n)中执行此操作.指向向量的中间并检查其邻居.如果它大于它的两个邻居,那么返回元素,它是一个峰值.如果右边的元素更大,则在数组的右侧递归地找到峰值.如果左边的元素更大,则在数组的左侧递归地找到峰值.

最糟糕的情况仍然是O(N) (9认同)
不,它是O(log n).说你的正确元素大于当前元素.然后你可以确定右边的序列包含一个峰值.因此,您将要查看的元素数量减半,从而产生O(log n).分而治之算法的好例子. (3认同)

Answer 2

是的,有可能以更好的时间复杂性找到它.使用devide和conquer方法