以比线性时间更好的方式查找三元组，使得A [n-1]> = A [n] <= A [n + 1]

Question

访谈中给出了一系列数字，例如A[0] >= A[1]和A[N-1] >= A[N-2]。我被要求找到至少一个三联体，例如A[n-1] >= A[n] <= A[n+1]。

我试着在迭代中解决。采访者期望比线性时间解决方案更好。我应该如何处理这个问题？

实施例：9 8 5 4 3 2 6 7

答案：3 2 6

Answer 1

线性你可以只通过所述一组迭代，比较它们都做。

你也可以检查前两个的斜率，然后做一种二进制斩波/按顺序遍历比较对，直到找到一个相反的斜率。这将分摊到一个好于n时间，我认为，虽然它不能保证。

编辑：刚刚意识到你的订购意味着什么。二进制斩波方法保证在<n时间内完成此操作，因为保证有一个变化点（假设N-1, N-2是列表的最后两个元素）。 这意味着你只需要找到它/他们中的一个，在这种情况下，二进制斩将采用分&治又名这么做是为了log(n)

Answer 2

我们可以解决这个在O(logn)时间。二进制搜索。好于线性时间。所以我们需要找到一个三元组，例如A[n-1] >= A[n] <= A[n+1]。

首先找到给定数组的中间值。如果mid比左边小，比右边大。然后返回，这就是你的答案。顺便说一下，这将是递归中的基本情况。另外如果len(arr) < 3那么太回。另一个basecase。

现在出现递归场景。何时递归，我们需要进一步检查权利。为此，如果mid大于其左侧的元素，则考虑将数组的左侧开始作为子问题，并使用此新数组进行递归。在这一点上有形的方面，即我们必须...2...与指数n被6.因此，我们向左移动，看是否元素的2左侧完成了三重。

否则，如果mid在其右侧子阵列上大于元素，则考虑数组右侧的mid + 1作为子问题并递归。

---

更多理论：以上应足以了解这个问题，但阅读。这个问题实质上归结为在一组给定元素中找到局部最小值。如果阵列中的数字小于其左侧和右侧数字，则数组中的数字称为局部最小值，其精确归结为A[n-1] >= A[n] <= A[n+1]。

一个给定的数组，使其前2个元素减少，最后2个元素增加HAS具有局部最小值。这是为什么？让我们通过否定来证明这一点。如果前两个数字减少，并且没有局部最小值，则意味着第三个数字小于第二个数字。否则第二个数字将是当地最低标准。遵循相同的逻辑第4个数字将不得不小于第3个数字等等等等。所以数组中的数字必须按照降序排列。这违背了最后两个数字按递增顺序的约束。这通过否定证明需要一个局部最小值。

上述理论认为一个O(n)线性的做法，但我们肯定可以做的更好。但是这个理论明确地给了我们关于这个问题的不同观点。

---

代码：这里的Python代码（仅供参考 - 在计算器的文本编辑器写意被输入，它可能misbheave）。

def local_minima(arr, start, end): 
    mid = (start+end)/2 

    if mid-2 < 0 and mid+1 >= len(arr): 
     return -1; 

    if arr[mid-2] > arr[mid-1] and arr[mid-1] < arr[mid]: #found it! 
     return mid-1; 

    if arr[mid-1] > arr[mid-2]: 
     return local_minima(arr, start, mid); 
    else: 
     return local_minima(arr, mid, end); 

请注意，我只是返回n的索引。要打印出三元组，只需执行-1和+1即可返回索引。 source

Answer 3

这听起来像你问的是：

你有数字的序列。它开始下降并继续下降，直到元素n，然后它开始增加，直到序列结束。找到n。

这是线性的时间（非最佳）的解决方案：

for (i = 1; i < length(A) - 1; i++) 
{ 
    if ((A[i-1] >= A[i]) && (A[i] <= A[i+1])) 
     return i; 
} 

做得比线性时间更好，你需要用你的事实得到了一系列减小后增大的信息。

考虑A[i]和A[i+1]之间的差异。如果A[i] > A[i+1]，那么n > i，因为值仍然在下降。如果A[i] <= A[i+1]，那么n <= i，因为值现在正在增加。在这种情况下，您需要检查A[i-1]和A[i]之间的差异。

这是在日志时间的解决方案：

int boundUpper = length(A) - 1; 
int boundLower = 1; 
int i = (boundUpper + boundLower)/2; //initial estimate 

while (true) 
{ 
    if (A[i] > A[i+1]) 
     boundLower = i + 1; 
    else if (A[i-1] >= A[i]) 
     return i; 
    else 
     boundUpper = i; 

    i = (boundLower + boundUpper)/2; 
} 

我将让你在必要的错误检查添加的情况下A没有满足条件的元素。