当数组中存在多个峰值时，如何找到峰值元素？

Question

当数组中存在多个峰值时，如何找到峰值元素？

javaarraysalgorithmbinary-search

5

针对具有单个峰值元素的数组，可以使用二分查找在o(logn)内完成，然而，在具有多个峰值元素的情况下，我们应该使用什么方法呢？

---添加更多信息----

峰值元素是指大于其相邻元素的元素。例如，看一下下面的数组：

[1,3,20,4,1,0,7,5,2]

它有两个峰值，20和7。

我们需要设计一个算法来找到这个数组中的峰值元素。

- brij

只按值排序吗？ - Gilles Lesire

2

多个峰值是什么意思？是指出现多次的最大值吗？为了进行二分查找，数组需要被排序。如果已经排序，这些峰值必须紧挨在一起，所以找到它们并不是一个问题，对吧？ - f1sh

1

@f1sh 我同意。如果OP在谈论一个相当数学的问题，我猜他是这样的，那么我也不会期望在任何地方看到二分搜索算法。他可能首先需要定义什么是“峰值”。它只是比其他值更大的值，还是比其他值“远远更大”的值？ “远远更大”是多少？我认为这个问题还没有被定义得足够好。 - Deniz

@brij，你打算如何在O(log n)的时间内搜索一个峰值？按照描述，这显然是不可能的。无论是一个峰值还是多个峰值，你都需要扫描整个数组，时间复杂度为O(n)。要注意第一个和最后一个元素。 - Abstraction

对于一个单峰元素，我们可以通过二分查找轻松实现。首先搜索中间元素，然后将其与相邻的元素进行比较，随后向左或向右移动到中间元素的一侧。找到中间元素的索引将中间元素与其邻居进行比较（如果存在邻居）如果中间元素不是峰值且其左侧邻居大于它，则左半部分必须有一个峰值元素如果中间元素不是峰值且其右侧邻居大于它，则右半部分必须有一个峰值元素 - brij

显示剩余8条评论

6个回答

1

我最近在一个编程网站上遇到了类似的问题，但除了要找峰值之外还有另一个重要限制。首先，可能会有多个峰值，但也可能出现高原！高原是指在一个数组中出现了 [1,2,2,2,1] 这样的情况，在这种情况下我们必须返回峰值为 2。在这个问题中，我们还被要求返回峰值第一次出现的位置，因此在这种情况下，位置应该是 1。唯一需要注意的情况是在数组 [1,2,2,2,3,4,5,1] 中，虽然有一系列看起来像高原的重复项，但在倒数第二个位置上确实存在一个峰值为 5 的峰，但却没有高原。

所以我考虑的基本算法是使用差分数组，如已建议使用{1,0,-1}，其中在连续流中获得一系列重复时使用0。每当我们在检查差分数组时得到0时，我们开始寻找第一个非零条目，无论它是1还是-1，并相应地输出。但是我们必须保持小心，因为可能差分数组看起来像Diff = [-1,1,-1,1,0,0,0]，在这种情况下没有高原，只有一个峰值。当输入arr时，Python代码如下：

n = len(arr)
if arr == []:
    return {"pos":[],"peaks":[]}
Diff = []
for i in range(0,n-1):
    if arr[i]< arr[i+1]:
        Diff.append(1)
    elif arr[i] == arr[i+1]:
        Diff.append(0)
    if arr[i] > arr[i+1]:
        Diff.append(-1)
pos = []
peaks = []
j = 0
for i in range(0,n-2):
    if Diff[i] == 1 and Diff[i+1] == -1:
        pos.append(i+1)
        peaks.append(arr[i+1])
    if Diff[i] == 1 and Diff[i+1] == 0:
        if Diff[i+1:] == [Diff[i+1]]:
            break
        j = i+1
        while(Diff[j] == 0 and j < n-2):
            j = j+1
        if Diff[j] == -1:
            pos.append(i+1)
            peaks.append(arr[i+1])


return {"pos":pos, "peaks":peaks}

- Sandra

0

当存在多个峰值时，查找所有峰元素。

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + right >> 1
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left

- aruns

0

int arr[] = {50, 12, 13, 20, 16, 19, 11, 7, 24};
int size = sizeof(arr) / sizeof(arr[0]);

int peak_arr[size / 2];
int i, j, k = 0;
int next, previous = 0;

for(i = 0; i < size; i++){
    if(i + 1 == size){
        next = 0;
    }
    else{
        next = arr[i + 1];
    }
    
    if(arr[i] > next && arr[i] >= previous){
        peak_arr[k++] = arr[i];
    }
    previous = arr[i];
}

- user14718775

尽管你的答案可能是正确的解决方案，但是加上一些关于你的代码的解释会更有帮助。 - Benjamin Zach

0

使用递归方法查找多个峰值元素。

def Div(lst, low, high):
    mid = (low + high)//2
    if low > high:
        return ""
    else:
        if mid+1 < len(lst) and lst[mid] > lst[mid+1] and lst[mid] > lst[mid -1]:
            return str(lst[mid]) + " " + Div(lst, low, mid-1) + Div(lst, mid+1, high)
        else:
            return Div(lst, low, mid-1) + Div(lst, mid + 1, high)

def peak(lst):
    if lst == []:
        return "list is empty"
    elif len(lst) in [1, 2]:
        return "No peak"
    else:
        return Div(lst, 0, len(lst))

print(peak([0, 5, 2, 9, 1, 10, 1]))

- Shayan Aamir

您的答案不是有效的Python代码，请编辑。 - Jari Turkia

@JariTurkia 代码已经修复。感谢您指出问题。我是StackOverflow的新手，不知道如何格式化代码。 - Shayan Aamir

-1

这个想法是使用修改后的二分查找。

如果 arr[mid+1]>arr[mid] 那么你的峰值总是存在于右半部分。

如果 arr[mid-1]>arr[mid] 那么你的峰值总是存在于左半部分。因为 arr[i+1] 只有两种可能，要么比 arr[i] 大，要么比 arr[i-1] 小。

我没有 Java 实现，但是这里有一个 Python 实现。

def FindAPeak(arr, i, j):
    mid = (i+j)/2
    # if mid element is peak
    if (mid == len(arr)-1 or arr[mid] > arr[mid+1]) and (mid == 0 or arr[mid] > arr[mid-1]):
        return arr[mid]
    # when your peak exists in the right half
    if arr[mid] < arr[mid+1] and mid+1 < len(arr):
        return FindAPeak(arr, mid+1, j)
    # when your peak exists in the left half
    else:
        return FindAPeak(arr, i, mid-1)


In [31]: arr = [1,2,3,2,1]
    ...: FindAPeak(arr, 0, len(arr)-1)
    ...: 
Out[31]: 3


In [32]: 
    ...: arr = [1,2,3,4,5,6]
    ...: FindAPeak(arr, 0, len(arr)-1)
    ...: 
Out[32]: 6

- aerin

1

不一定，另一侧仍可能存在峰值，因此要找到所有峰值，上述算法是错误的。例如：5,4,3,2,1,0,5,2 两侧都有峰值。 - Sid

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hakes · Accepted Answer

我可能没有理解你的问题，因为要在O(logn)时间内找到单个峰值需要首先对数组进行排序。

我建议您存储一个差分数组，它将生成如下输出：[1,3,20,4,1,0,7,5,2] => [1, 1,-1,-1,-1, 1,-1,-1]，这只是在数组中放置增加方向的大小为n - 1的数组。这可以在O(n)的单次遍历中完成。

第二次遍历时，您将寻找[1, -1]对，这是峰值发生的地方。

如果您想在开头和结尾找到峰值，您需要检查开头是否为-1，结尾是否为1。

希望这有所帮助。