寻找局部极小的数组 [英] Find local minima in an array

问题描述

由于整数数组，寻找局部极小。一个元素a [i]的定义为局部极小，如果A [I-1]> A [i]和A [1] - ; A [I + 1]，其中i = 1，...，N-2。如果边界的元素，这个数字已经是公正比其相邻的数字更小的。

Given an array of integers, find the local minima. An element A[i] is defined as a local minimum if A[i-1] > A[i] and A[i] < A[i+1] where i = 1...n-2. In case of boundary elements, the number has to be just smaller than its adjacent number.

我知道，如果只有一个局部最小，那么我们就可以用修改二进制搜索解决。 但是，如果知道有数组中存在多个局部极小，可以将其在 O（log n）的时间？

I know if there is only one local minimum, then we can solve with modified binary search. But if it is known that there exist multiple local minima in the array, can it be solved in O(log n) time?

推荐答案

如果数组中的元素都不能保证是不同的，那么它是不可能做到这一点的O（log n）的时间。其原因如下：假设你有一个数组，其中所有的n> 1的值是相同的。在这种情况下，没有元件可以是局部极小，因为没有元件低于其邻居。然而，为了确定所有的值都是一样的，你将不得不考虑所有的数组元素，这需要O（n）的时间。如果不是O（n）的时间少用，你不一定能看到所有的数组元素。

If the array elements are not guaranteed to be distinct, then it's not possible to do this in O(log n) time. The reason for this is the following: suppose that you have an array where all n > 1 values are the same. In this case, none of the elements can be local minima, because no element is less than its neighbors. However, in order to determine that all values are the same, you will have to look at all the array elements, which takes O(n) time. If you use less than O(n) time, you can't necessarily look at all the array elements.

如果，在另一方面，数组元素保证是不同的，你可以在O解决这个使用下面的意见（log n）的时间：

If, on the other hand, the array elements are guaranteed to be distinct, you can solve this in O(log n) time using the following observations:

1. 如果只有一个元素，它的保证是局部极小。
2. 如果有多个元素，看看中间元素。如果它是一个局部最小，就大功告成了。否则，该元素中的至少一个在它旁边必须比它小。现在，想象一下，如果你要开始的较小的元素之一，并逐渐朝离开的方向从中间元件阵列的端部之一移动会发生什么。在每一步，无论是下一个元素比previous小，否则就会更大。最终，你要么打数组的结尾这样一来，否则你将达到当地最低。请注意，这意味着您可以这样做是为了找到当地的最低水平。但是，我们实际上并不打算这样做。相反，我们将使用一个当地最低将存在在这半年的数组作为一个理由扔阵而去一半的事实。在剩下，我们肯定可以找到一个局部最小值。

1. If there is just one element, it's guaranteed to be a local minimum.
2. If there are multiple elements, look at the middle element. If it's a local minimum, you're done. Otherwise, at least one of the elements next to it must be smaller than it. Now, imagine what would happen if you were to start at one of the smaller elements and progressively move toward one of the ends of the array in the direction away from the middle element. At each step, either the next element is smaller than the previous, or it will be bigger. Eventually, you will either hit the end of the array this way, or you will hit a local minimum. Note that this means that you could do this to find a local minimum. However, we're not actually going to do that. Instead, we'll use the fact that a local minimum will exist in this half of the array as a justification for throwing away one half of the array. In what remains, we are guaranteed to find a local minimum.

因此​​，你可以建立以下递归算法：

Consequently, you can build up the following recursive algorithm:

1. 如果只有一个数组元素，它是一个局部最小值。
2. 如果有两个数组元素，检查每个。其中一个必须是本地最低程度。
3. 否则，看看数组的中间元素。如果它是一个局部最小值，返回。否则，在至少一个相邻的值必须比这小。递归在包含阵列的一半更小的元素（但不包括中间）。

请注意，这有递推关系

T（1）与乐; 1

T(1) ≤ 1

T（2）与乐; 1

T(2) ≤ 1

T（N）与乐; T（N / 2）+1

T(n) ≤ T(n / 2) + 1

使用主定理，可以证明，该算法的时间为O（log n）的运行，并按要求。

Using the Master Theorem, you can show that this algorithm runs in time O(log n), as required.

希望这有助于！

请还会注意到，该算法只有当阵列的边缘算作局部极小，如果它们比相邻的元素小。

Please also notice that this algorithm only works if edges of the array count as local minima if they are smaller than the adjacent element.

这篇关于寻找局部极小的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！