C语言中数组的峰值元素

Question

我被给定了一个整数数组，需要找到其中的峰值元素。 如果一个数组元素不小于它的相邻元素，则该元素为峰值元素。 对于边缘元素，只考虑一个相邻元素。

例如：

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

我尝试的解决方法是线性扫描数组并找到峰值元素。该方法的最坏时间复杂度为O(n)。

我们能否在最坏时间复杂度优于O(n)的情况下找到峰值元素？

- poorvank

---

我认为，你需要检查该数组的所有元素，因此O(n)是最低的。 - Jayan

Answer 1

是的，你可以使用类似二分查找的思想在O(log n)时间复杂度内完成。指向向量的中间元素并检查其相邻元素。如果它比两个相邻元素都大，则返回该元素，它就是峰值。如果右侧元素更大，则在数组的右侧递归查找峰值。如果左侧元素更大，则在数组的左侧递归查找峰值。

- Daniel Martín

---

不，时间复杂度为O(log n)。假设右侧元素大于当前元素，则可以确定右侧序列包含峰值。因此，您已将需要查看的元素数量减半，时间复杂度为O(log n)。这是分治算法的很好例子。 - Thilo

在这个问题中，我们不需要寻找。因为给出一个元素和它的右邻居（例如），我们可以保证右侧存在峰值，如果邻居大于中心点：如果所有元素继续增加，峰值是数组的右极端；如果下一个元素小于邻居，则邻居是峰值。对于任何其他情况，递归处理。 - Daniel Martín

假设您看向右侧，因此右侧的元素比当前元素大。现在我们只有两个选择：右侧的元素是峰值，或者它旁边的元素仍然更大。重复此过程，直到找到峰值或到达序列的末尾，这时根据定义，它就是峰值。因此，一旦向右移动，您肯定会找到峰值。 - Thilo

https://dev59.com/xXLYa4cB1Zd3GeqPcNf5#16887717 - SomeWittyUsername

@Dariusz 不对，它是O(log n)。在最坏情况下，您永远不会遍历所有元素。最佳情况是O(1)，平均和最坏情况是O(log n)。 - Shashank

Answer 2

是的，可以使用分治算法以更好的时间复杂度找到它。

以下链接将对您有所帮助。 http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

- rahul.deshmukhpatil

Answer 3

根据其他人的答案（在我下面），以下是一些具有 O(log n) 的代码：

// A divide and conquer solution to find a peak element element
#include <stdio.h>

// A binary search based function that returns index of a peak element
int findPeakUtil(int arr[], int low, int high, int n)
{
    // Fin index of middle element
    int mid = low + (high - low)/2;  /* (low + high)/2 */

    // Compare middle element with its neighbours (if neighbours exist)
    if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
            (mid == n-1 || arr[mid+1] <= arr[mid]))
        return mid;

    // If middle element is not peak and its left neighbor is greater than it
    // then left half must have a peak element
    else if (mid > 0 && arr[mid-1] > arr[mid])
        return findPeakUtil(arr, low, (mid -1), n);

    // If middle element is not peak and its right neighbor is greater than it
    // then right half must have a peak element
    else return findPeakUtil(arr, (mid + 1), high, n);
}

// A wrapper over recursive function findPeakUtil()
int findPeak(int arr[], int n)
{
    return findPeakUtil(arr, 0, n-1, n);
}

/* Driver program to check above functions */
int main()
{
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Index of a peak point is %d", findPeak(arr, n));
    return 0;
}

我曾在MIT 6.006 OCW课程中使用过这个工具，您也可以去看看。

http://courses.csail.mit.edu/6.006/spring11/rec/rec02.pdf

- Soumik Das

---

@mobbarley，如何仅搜索大峰值（而不是每个峰值，例如比邻居高100）？ - josef

这段代码不应该有赞。它没有找到峰值。 - Bright Lee

这段代码不是找到峰值，而是找到峰值的索引。您可以使用该索引来获取峰值元素。还可以参考实时示例。https://repl.it/DgBs/1 - Soumik Das