针对具有单个峰值元素的数组,可以使用二分查找在o(logn)内完成,然而,在具有多个峰值元素的情况下,我们应该使用什么方法呢?
---添加更多信息----
峰值元素是指大于其相邻元素的元素。例如,看一下下面的数组:
[1,3,20,4,1,0,7,5,2]
它有两个峰值,20和7。
我们需要设计一个算法来找到这个数组中的峰值元素。
---添加更多信息----
峰值元素是指大于其相邻元素的元素。例如,看一下下面的数组:
[1,3,20,4,1,0,7,5,2]
它有两个峰值,20和7。
我们需要设计一个算法来找到这个数组中的峰值元素。
[1,3,20,4,1,0,7,5,2]
=> [1, 1,-1,-1,-1, 1,-1,-1]
,这只是在数组中放置增加方向的大小为n - 1
的数组。这可以在O(n)的单次遍历中完成。所以我考虑的基本算法是使用差分数组,如已建议使用{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}
当存在多个峰值时,查找所有峰元素。
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
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];
}
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]))
这个想法是使用修改后的二分查找。
如果 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