6

给定一个数组a[]，确定至少一个元素是否i满足条件的最有效方法是a[i] == i什么？

数组中的所有元素都已排序且不同，但它们不一定是整数类型（即它们可能是浮点类型）。

4

6 回答 6

8

一些人声称“排序”、“不同”和“不一定是整数”的相关性。事实上，正确选择有效的算法来解决这个问题取决于这些特征。如果我们可以知道数组中的值既是不同的又是整数的，那么更有效的算法将是可能的，而如果这些值可能是非不同的，无论它们是否是整数，则需要一种效率较低的算法。当然，如果数组还没有排序，你可以先排序（平均复杂度 O(n log n)），然后使用更有效的预排序算法（即排序数组），但在未排序的在这种情况下，简单地将数组保持未排序并直接比较线性时间（O（n））中的值会更有效。请注意，无论选择哪种算法，最佳情况下的性能都是 O(1)（当检查的第一个元素包含其索引值时）；在执行任何算法期间的任何时候，我们都可能遇到一个元素a[i] == i此时我们返回 true；在这个问题中，就算法性能而言，真正重要的是我们可以多快排除所有元素并声明没有这样的元素a[i]where a[i] == i。

问题没有说明 的排序顺序a[]，这是一个非常关键的缺失信息。如果它是递增的，最坏情况的复杂度将始终为 O(n)，我们无法做任何事情来使最坏情况的复杂度更好。但是如果排序顺序是降序的，即使是最坏情况的复杂度也是 O(log n)：因为数组中的值是不同的并且是降序的，所以只有一个可能的索引a[i]可以 equal i，基本上你所要做的就是二分查找找到交叉点（升序索引值与降序元素值交叉的地方，如果甚至有这样的交叉），并确定是否a[c] == c在交叉点索引值c. 由于这很简单，我将继续假设排序顺序是升序的。有趣的是，如果元素是整数，即使在升序情况下也会出现类似的“类似交叉”的情况（尽管在升序情况下可能会有不止一个a[i] == i匹配），所以如果元素是整数，二分查找也将是适用于升序情况，在这种情况下，即使是最坏情况的性能也是 O(log n) （请参阅面试问题 - 在排序数组 X 中搜索索引 i 使得 X[i] = i）。但在这个版本的问题中，我们并没有得到那种奢侈。

以下是我们可能解决此问题的方法：

从第一个元素 开始a[0]。如果它的值为== 0，则您已找到满足的元素，a[i] == i因此返回 true。如果其值为< 1，则下一个元素 ( a[1]) 可能包含该值1，因此您继续下一个索引。但是，如果a[0] >= 1您知道（因为值不同）条件a[1] == 1不可能为真，那么您可以安全地跳过 index 1。但是您甚至可以做得更好：例如，如果a[0] == 12，您知道（因为值按升序排序）不可能有任何元素满足a[i] == i元素之前a[13]. 因为数组中的值可以是非整数的，所以我们现在不能做任何进一步的假设，所以我们可以安全地直接跳到的下一个元素是a[13]（例如a[1]througha[12]可能都包含介于12.000...and之间的值，13.000...这样a[13]仍然可以完全相等13，所以我们必须检查它）。

继续该过程会产生如下算法：

// Algorithm 1
bool algorithm1(double* a, size_t len)
{
    for (size_t i=0; i<len; ++i) // worst case is O(n)
    {
        if (a[i] == i)
            return true; // of course we could also return i here (as an int)...
        if (a[i] > i)
            i = static_cast<size_t>(std::floor(a[i]));
    }
    return false; // ......in which case we’d want to return -1 here (an int)
}

a[]如果 in中的许多值大于它们的索引值，这具有相当好的性能，并且如果 in 中的所有值a[]都大于 n，则具有出色的性能（仅在一次迭代后返回 false！），但如果所有值都小于它们的索引值（它会在 n 次迭代后返回 false）。所以我们回到绘图板......但我们需要的只是轻微的调整。考虑到该算法可以被编写为从 n 向下扫描到 0，就像它可以从 0 向前扫描到 n 一样容易。如果我们结合从两端向中间迭代的逻辑，我们得到一个算法如下：

// Algorithm 2
bool algorithm2(double* a, size_t len)
{
    for (size_t i=0, j=len-1; i<j; ++i,--j) // worst case is still O(n)
    {
        if (a[i]==i || a[j]==j)
            return true;
        if (a[i] > i)
            i = static_cast<size_t>(std::floor(a[i]));
        if (a[j] < j)
            j = static_cast<size_t>(std::ceil(a[j]));
    }
    return false;
}

这在两种极端情况下都具有出色的性能（所有值都小于 0 或大于 n），并且在几乎任何其他值分布情况下都具有非常好的性能。最坏的情况是如果数组下半部分的所有值都小于它们的索引，并且上半部分的所有值都大于它们的索引，在这种情况下性能会下降到 O( n)。最好的情况（极端情况）是O（1），而平均情况可能是O（log n），但我要让数学专业的人确定这一点。

一些人提出了一种“分而治之”的方法来解决这个问题，但没有具体说明如何划分问题以及如何处理递归划分的子问题。当然，这样一个不完整的答案可能不会让面试官满意。上面算法 2 的朴素线性算法和最坏情况下的性能都是 O(n)，而算法 2 通过尽可能跳过（不检查）元素将平均情况下的性能提高到（可能）O(log n)。分而治之的方法只能胜过算法 2，如果在平均情况下，它能够以某种方式跳过比算法 2 可以跳过的更多的元素。假设我们通过递归地将数组分成两个（几乎）相等的连续两半来划分问题，并决定是否使用产生的子问题，我们可能会跳过比算法 2 可以跳过的更多的元素，尤其是在算法 2 最坏的情况下。对于本讨论的其余部分，让我们假设输入对于算法 2 来说是最坏的情况。在第一次拆分之后，我们可以检查两半的顶部和底部元素是否存在导致 O(1) 性能的相同极端情况算法2，但结果是两半相结合的 O(n) 性能。如果下半部分的所有元素都小于 0 并且上半部分的所有元素都大于 n-1，就会出现这种情况。在这些情况下，对于我们可以排除的任何一半，我们可以立即以 O(1) 的性能排除下半部分和/或上半部分。当然，该测试不能排除的任何一半的性能仍有待进一步递归后确定，再次将其除以一半，直到我们找到顶部或底部元素包含其索引值的任何段。与算法 2 相比，这是一个相当不错的性能改进，但它仅发生在算法 2 最坏情况的某些特殊情况下。我们通过分而治之所做的只是减少（稍微）引起最坏情况行为的问题空间的比例。分而治之仍然存在最坏情况，它们与引发算法 2 最坏情况行为的大多数问题空间完全匹配。我们通过分而治之所做的只是减少（稍微）引起最坏情况行为的问题空间的比例。分而治之仍然存在最坏情况，并且它们与引发算法 2 最坏情况行为的大多数问题空间完全匹配。我们通过分而治之所做的只是减少（稍微）引起最坏情况行为的问题空间的比例。分而治之仍然存在最坏情况，并且它们与引发算法 2 最坏情况行为的大多数问题空间完全匹配。

那么，鉴于分而治之算法的最坏情况较少，继续使用分而治之的方法是否有意义？

一句话，没有。也许。如果您预先知道大约一半的数据小于 0，一半大于 n，那么这种特殊情况通常会采用分而治之的方法更好。或者，如果您的系统是多核的并且您的“n”很大，那么在所有核心之间平均分配问题可能会有所帮助，但是一旦在它们之间分配，我认为每个核心上的子问题可能是最好的用上面的算法 2 解决了，避免了问题的进一步划分，当然也避免了递归，正如我在下面讨论的......

在递归分治法的每个递归级别，算法需要某种方法来记住问题的尚未解决的第二半部分，同时它会递归到第一半部分。这通常是通过让算法首先递归地调用自己的一半然后再调用另一半来完成的，这种设计在运行时堆栈上隐式地维护此信息。另一种实现可能通过在显式堆栈上维护基本相同的信息来避免递归函数调用。在空间增长方面，算法 2 是 O(1)，但任何递归实现都不可避免地是 O(log n)，因为必须在某种堆栈上维护此信息。但除了空间问题，递归实现具有额外的运行时开销，需要记住尚未递归进入的子问题一半的状态，直到它们可以递归进入。这种运行时开销不是免费的，并且鉴于上述算法 2 的实现的简单性，我认为这种开销成比例地显着。因此，我建议上面的算法 2 将对绝大多数情况进行全面的递归实现。

于 2012-12-01T23:27:46.713 回答
4

在最坏的情况下，你不能比检查每个元素做得更好。（想象一下类似的东西a[i] = i + uniform_random(-.25, .25)。）你需要一些关于你的输入是什么样子的信息。

于 2012-11-29T19:15:01.617 回答
1

实际上我会从最后一个元素开始，做一个基本的检查（例如，如果你有 1000 个元素，但最高是 100，你知道你只需要检查 0..100）。在最坏的情况下，您仍然需要检查每个元素，但找到可能的区域应该更快。如果如上所述（a[i] = i + [-0.25..0.25]），那么您就是 f($!ed，需要搜索每个元素。

于 2012-11-29T20:10:50.053 回答
0

我认为这里的主要问题是您的相互矛盾的陈述：

a[i] ==我

数组中的所有元素都是有序且不同的，它们不必总是整数。

如果数组的值等于它的访问下标，这意味着它是一个整数。如果它不是整数，并且他们说.. char，那么什么被认为是“排序的”？ASCII 值 ( A < B < C)？

如果它是一个字符数组，我们会考虑：

a[i] == i

如果是真的

i == 65 10 && a[i] == 'A'

如果我在这次面试中，我会在回答之前向面试官询问后续问题。那就是说...

如果我们所知道的就是您所说的，我们可以肯定地说我们可以在 O(n) 中找到值，因为这是对数组进行一次完整传递的时间。有了更多细节，我们可以通过对数组的二进制搜索将其限制为 O(log(n))。

于 2012-11-29T19:58:00.210 回答
0

对于排序数组，您可以执行插值搜索。类似于二分搜索，但假设值分布均匀，可以更快。

于 2012-11-29T19:07:54.247 回答
0

注意到数组中的所有元素都是有序且不同的，所以如果我们用b[i]=a[i]-i构造一个新的数组b，数组b中的元素也是有序的，我们需要找到的是找到数组 b 中的零。我认为二分查找可以解决问题！这是一个用于计算排序数组中出现次数的链接。您也可以在原始数组上执行类似的分治技术，而无需构造辅助数组！时间复杂度为 O(Logn)！

Take this as an example:
a=[0,1,2,4,8]
b=[0,0,0,1,4]
What we need to find is exactly index 0,1,2

希望能帮助到你！

于 2012-12-01T07:12:50.790 回答