找到优于线性时间的三元组,使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

我们可以O(logn)使用divide&conquer aka 来及时解决这个问题.二分搜索.比线性时间更好.所以我们需要找到这样的三元组A[n-1] >= A[n] <= A[n+1].

首先找到给定数组的中间位置.如果mid小于其左侧且大于右侧.然后回来,这就是你的答案.顺便说一下,这将是递归的基础.如果len(arr) < 3那时也回归.另一个基础.

现在出现了递归方案.何时递归,我们需要进一步检查.为此,如果mid大于其左侧的元素,则将数组的左起点视为子问题,并使用此新数组进行递归.也就是说,在这一点上我们将有...26个...索引n为6.所以我们向左移动以查看左边的元素是否2完成了三元组.

否则,如果mid大于其右子阵列上的元素,则将数组的mid + 1到right视为子问题并递归.

更多理论:上述内容应足以理解问题,但请继续阅读.问题基本上归结为在给定的元素集中找到局部最小值.数组中的数字称为局部最小值,如果它小于其左右数字,精确归结为A[n-1] >= A[n] <= A[n+1].

给定的数组使其前2个元素减少,最后2个元素增加HAS以具有局部最小值.这是为什么？让我们通过否定来证明这一点.如果前两个数字正在减少,并且没有局部最小值,则表示第三个数字小于第二个数字.否则第二个数字将是当地的最小值.遵循相同的逻辑,第四个数字必须小于第三个数字,依此类推.因此,数组中的数字必须按递减顺序排列.这违反了最后两个数字的增加顺序的约束.这通过否定证明需要有一个局部最小值.

上述理论提出了O(n)线性方法,但我们肯定能做得更好.但这个理论肯定会让我们对这个问题有不同的看法.

代码:这是python代码(fyi - 在stackoverflow文本编辑器中徒手输入,它可能会错误地写入).

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返回索引.资源

Answer 2

您可以通过迭代集合并比较它们来实现线性。

您还可以检查前两个的斜率，然后进行一种二元斩波/中序遍历比较对，直到找到相反的斜率之一。我认为，这会比n时间更好地摊销，尽管不能保证。

编辑：刚刚意识到您的订购意味着什么。二元砍伐方法保证及时执行此操作<n，因为保证有一个更改点（假设您N-1, N-2是列表的最后两个元素）。这意味着您只需要找到它/其中之一，在这种情况下，二进制砍将按顺序完成log(n)