10

在一次采访中给出了一系列数字，使得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

4

3 回答 3

9

我们可以O(logn)使用分而治之的方法及时解决这个问题。二进制搜索。比线性时间好。所以我们需要找到一个这样的三元组A[n-1] >= A[n] <= A[n+1]。

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

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

否则，如果 mid 大于其右子数组上的元素，则将数组右侧的 mid+1 视为子问题并递归。

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

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

上述理论提出了一种O(n)线性方法，但我们绝对可以做得更好。但是这个理论肯定给了我们关于这个问题的不同视角。

代码：这是 python 代码（仅供参考 - 是在 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返回到返回的索引。资源

于 2013-07-12T04:31:51.150 回答
2

听起来您要问的是这样的：

你有一个数字序列。它开始减少并继续减少直到 element 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如果没有满足条件的元素，我将留给您添加必要的错误检查。

于 2013-07-12T04:43:32.147 回答
1

线性，你可以通过迭代集合，比较它们来完成。

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

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

于 2013-07-12T04:07:13.433 回答