java - 找到给定数组的一维峰

Question

我正在为一维数组编写寻峰算法代码。我读过这篇文章Peak finding algorithm .这正是我想要做的，有关于时间复杂度的讨论，但没有任何伪代码。问题:

Given an array [a,b,c,d,e,f,g] where a to g are numbers, b is a peak if and only if a<=b and b>=c.

示例:给定一个数组 {1,2,3,4,5,19,25,20} , 指数 6应该退回。边缘情况应该给出:

{100,4,3,1,19,20} -- index 0

{1,3,5,19,20} -- index 4

我已经在 Java 中实现了.我当前的运行时间是 O(n) .我想知道这是否可以改进

public static int naive(int[] arr){
        int l=arr.length;
        if (arr[0]>=arr[1]) {
            return 0;
        }
        if (arr[l-1]>arr[l-2]){
            return l-1;
        }
        for (int i=1; i < arr.length-1;i++){
             if (arr[i] >= arr[i-1] && arr[i] >= arr[i+1] ){
                 return i;
             }
        }
        return -1;
    }

Answer 1

以下函数可能比您的函数效率高一点点。请注意，这将找到一个局部最大值。

    public static int findLocalMaximum(int[] arr){
        int i = 0;
        while(i + 1 < arr.length && arr[i+1] >= arr[i]) {
            ++i;
        }
        return i;
    }

编辑:以下函数查找问题中定义的峰值。请注意，我删除了 while 循环中的边界检查，因为只有在 arr[l-2] > arr[l-1] 时才会到达循环，因此 while 循环中的条件将为 false，l-2 将被返回。

    public static int findPeak(int[] arr){
        int l = arr.length;
        if(arr[0] >= arr[1]) {
            return 0;
        }

        if(arr[l-1] >= arr[l-2]) {
            return l-1;
        }

        int i = 1;
        while(arr[i+1] > arr[i]) {
            ++i;
        }
        return i;
    }