dsal 查找峰值元素

查找峰值元素

原文： https://www.geeksforgeeks.org/find-a-peak-in-a-given-array/

给定一个整数数组。在其中找到一个峰元素。如果数组元素不小于其邻居，则它是一个峰。对于角落元素，我们只需要考虑一个邻居。

示例：

Input: array[]= {5, 10, 20, 15}
Output: 20
The element 20 has neighbours 10 and 15,
both of them are less than 20.

Input: array[] = {10, 20, 15, 2, 23, 90, 67}
Output: 20 or 90
The element 20 has neighbours 10 and 15, 
both of them are less than 20, similarly 90 has neighbous 23 and 67.

在遇到严重问题时，可以更好地解决此问题。

如果输入数组严格按升序排序，则最后一个元素始终是峰值元素。例如，50 是{10, 20, 30, 40, 50}中的峰值元素。
如果输入数组按严格降序排序，则第一个元素始终是峰元素。 100 是{100, 80, 60, 50, 20}中的峰值元素。
如果输入数组的所有元素都相同，则每个元素都是峰值元素。

从上面的示例可以清楚地看出，输入数组中始终存在一个峰值元素。

朴素的方法：可以遍历数组，并且可以返回其邻居小于该元素的元素。

算法：

如果在数组中，第一个元素大于第二个元素或最后一个元素大于倒数第二个元素，则打印相应的元素并终止程序。
否则将数组从第二个索引遍历到第二个最后一个索引.
如果对于元素array[i]，它大于其相邻元素，即arrayx[i] > array[i-1]和array[i] > array[i + 1]，然后打印该元素并终止。

// A C++ program to find a peak element 
#include <bits/stdc++.h> 
using namespace std; 

// Find the peak element in the array 
int findPeak(int arr[], int n) 
{ 
    // first or last element is peak element 
    if (n == 1)  
      return arr[0]; 
    if (arr[0] >= arr[1]) 
        return 0; 
    if (arr[n - 1] >= arr[n - 2]) 
        return n - 1; 

    // check for every other element 
    for (int i = 1; i < n - 1; i++) { 

        // check if the neighbors are smaller 
        if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) 
            return i; 
    } 
} 

// Driver Code 
int main() 
{ 
    int arr[] = { 1, 3, 20, 4, 1, 0 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Index of a peak point is "
         << findPeak(arr, n); 
    return 0; 
} 

// This code is contributed by Arnab Kundu

输出：

Index of a peak point is 2

复杂度分析：

时间复杂度：O(n)。

需要进行一次遍历，因此时间复杂度为O(n)。
空间复杂度：O(1)。

不需要多余的空间，因此空间复杂度是恒定的。

高效方法：分治可用于查找O(Logn)时间的峰值。这个想法是基于二分搜索技术来检查中间元素是否是峰值元素。如果中间元素不是峰值元素，则检查右侧的元素是否大于中间元素，那么右侧总是存在一个峰值元素。如果左侧的元素大于中间的元素，则左侧总是有一个峰值元素。形成递归，峰值元素可以在log n时间内找到。

算法：

创建两个变量l和r，初始化l = 0和r = n-1。
重复以下步骤，直到l <= r，下限小于上限。
检查中值或索引mid = (l + r) / 2是否是峰值元素，如果是，则打印该元素并终止。
否则，如果中间元素左侧的元素更大，则检查左侧的峰值元素，即更新r = mid – 1。
否则，如果中间元素右侧的元素较大，则检查右侧的峰元素，即更新l = mid + 1。

C++

// A C++ program to find a peak element 
// using divide and conquer 
#include <bits/stdc++.h> 
using namespace std; 

// A binary search based function 
// that returns index of a peak element 
int findPeakUtil(int arr[], int low, 
                 int high, int n) 
{ 
    // Find index of middle element 
    // (low + high)/2 
    int mid = low + (high - low) / 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 neighbour 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 neighbour 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 Code 
int main() 
{ 
    int arr[] = { 1, 3, 20, 4, 1, 0 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Index of a peak point is "
         << findPeak(arr, n); 
    return 0; 
} 

// This code is contributed by rathbhupendra

C

// C program to find a peak 
// element using divide and conquer 
#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) 
{ 
    // Find index of middle element 
    // (low + high)/2 
    int mid = low + (high - low) / 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 neighbour 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 neighbour 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; 
}

Java

// A Java program to find a peak 
// element using divide and conquer 
import java.util.*; 
import java.lang.*; 
import java.io.*; 

class PeakElement { 
    // A binary search based function 
    // that returns index of a peak element 
    static int findPeakUtil( 
        int arr[], int low, int high, int n) 
    { 
        // Find index of middle element 
        // (low + high)/2 
        int mid = low + (high - low) / 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() 
    static int findPeak(int arr[], int n) 
    { 
        return findPeakUtil(arr, 0, n - 1, n); 
    } 

    // Driver method 
    public static void main(String[] args) 
    { 
        int arr[] = { 1, 3, 20, 4, 1, 0 }; 
        int n = arr.length; 
        System.out.println( 
            "Index of a peak point is " + findPeak(arr, n)); 
    } 
}

Python3

# A python 3 program to find a peak  
# element element using divide and conquer 

# A binary search based function  
# that returns index of a peak element 
def findPeakUtil(arr, low, high, n): 

     # Find index of middle element 
     # (low + high)/2  
     mid = low + (high - low)/2 
     mid = int(mid) 

    # Compare middle element with its  
    # neighbours (if neighbours exist) 
    if ((mid == 0 or arr[mid - 1] <= arr[mid]) and 
        (mid == n - 1 or arr[mid + 1] <= arr[mid])): 
        return mid 

    # If middle element is not peak and  
    # its left neighbour is greater  
    # than it, then left half must  
    # have a peak element 
    elif (mid > 0 and arr[mid - 1] > arr[mid]): 
        return findPeakUtil(arr, low, (mid - 1), n) 

    # If middle element is not peak and 
    # its right neighbour 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() 
def findPeak(arr, n): 

    return findPeakUtil(arr, 0, n - 1, n) 

# Driver code 
arr = [1, 3, 20, 4, 1, 0] 
n = len(arr) 
print("Index of a peak point is", findPeak(arr, n)) 

# This code is contributed by  
# Smitha Dinesh Semwal

C#

// A C# program to find 
// a peak element element 
// using divide and conquer 
using System; 

class GFG { 

    // A binary search based 
    // function that returns 
    // index of a peak element 
    static int findPeakUtil(int[] arr, int low, 
                            int high, int n) 
    { 
        // Find index of 
        // middle element 
        int mid = low + (high - low) / 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() 
    static int findPeak(int[] arr, 
                        int n) 
    { 
        return findPeakUtil(arr, 0, 
                            n - 1, n); 
    } 

    // Driver Code 
    static public void Main() 
    { 
        int[] arr = { 1, 3, 20, 
                      4, 1, 0 }; 
        int n = arr.Length; 
        Console.WriteLine("Index of a peak "
                          + "point is " + findPeak(arr, n)); 
    } 
} 

// This code is contributed by ajit

PHP

<?php 
// A PHP program to find a  
// peak element element using 
// divide and conquer 

// A binary search based function 
// that returns index of a peak  
// element 
function findPeakUtil($arr, $low,  
                      $high, $n) 
{ 
    // Find index of middle element 
    $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 neighbour 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 neighbour 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() 
function findPeak($arr, $n) 
{ 
    return floor(findPeakUtil($arr, 0,  
                              $n - 1, $n)); 
} 

// Driver Code 
$arr = array(1, 3, 20, 4, 1, 0); 
$n = sizeof($arr); 
echo "Index of a peak point is ",  
              findPeak($arr, $n); 

// This code is contributed by ajit 
?>

输出：

Index of a peak point is 2

复杂度分析：

时间复杂度：O(log n)。

其中n是输入数组中元素的数量。在每一步中，我们的搜索将变成一半。因此可以将其与二分搜索进行比较，因此时间复杂度为O(log n)。
空间复杂度：O(1)。

不需要额外的空间，因此空间复杂度是恒定的。

练习：

考虑峰元素的以下修改定义。如果数组元素大于其邻居元素，则它是一个峰。注意，数组可能不包含具有此修改后定义的峰值元素。

参考：

http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

(http://www.youtube.com/watch?v=HtSuA80QTyo

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-17》

分类

最近更新

dsal 查找峰值元素

查找峰值元素

C++

C

Java

Python3

C#

PHP

询问：亚马逊

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-17》

dsal 查找峰值元素

查找峰值元素

C++

C

Java

Python3

C#

PHP

询问：亚马逊

留言

联系客服

dsal 查看更多书籍