有几个人声称"排序","不同"和"不一定是整数"的相关性.实际上,正确选择有效的算法来解决这个问题取决于这些特性.如果我们知道数组中的值既是不同的又是积分的,那么更有效的算法是可能的,而如果值可能是非不同的,则需要效率较低的算法,无论它们是否是整数.当然,如果数组尚未排序,您可以先对其进行排序(平均复杂度为O(n log n)),然后使用更有效的预排序算法(即对于排序的数组),但在未排序的情况下例如,简单地保持数组未排序并直接比较线性时间(O(n))中的值会更有效.请注意,无论选择何种算法,最佳情况都是O(1)(当检查的第一个元素包含其索引值时); 在执行任何算法的任何时候,我们都可能遇到一个元素,a[i] == i在这一点上我们返回true; 什么在这个问题的算法性能方面其实重要的是我们如何能迅速排除所有元素,并声明不存在这样的元素a[i]在那里a[i] == i.
问题没有说明排序顺序a[],这是一个非常重要的缺失信息.如果它是递增的,最坏情况下的复杂性将始终为O(n),我们无法做任何事情来使最坏情况的复杂性更好.但是如果排序顺序下降,即使是最坏情况下的复杂度也是O(log n):因为数组中的值是不同的并且是降序的,所以只有一个可能的索引a[i]可以相等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不可能为真,那么您可以安全地跳过索引1.但你甚至可以做得更好:例如,如果a[0] == 12你知道(因为值按升序排序),那么就不可能有任何元素a[i] == i在元素之前满足a[13].因为数组中的值可以是非整数,我们不能在这一点上任何进一步的假设,那么下一个元素,我们可以跳过,直接是a[13](例如a[1]通过a[12]可能都含有之间的值12.000...,并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[]都大于它们的索引值,那么它具有相当好的性能,并且如果所有值a[]都大于n(在仅一次迭代后它返回false,则具有出色的性能),但如果所有值都是小于它们的索引值(在n次迭代后它将返回false).所以我们回到绘图板......但我们所需要的只是略微调整.考虑到算法可能已被编写为从n向下扫描到0,就像它可以从0向前扫描一样容易.如果我们将迭代的逻辑从两端组合到中间,我们得到如下算法:
// 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的最坏情况行为.
因此,鉴于分而治之的算法具有较少的最坏情况,继续使用分而治之的方法是不是有意义？
总之,没有.也许.如果您事先知道大约一半的数据小于0且一半大于n,那么这种特殊情况通常会采用分而治之的方法.或者,如果您的系统是多核的并且您的'n'很大,那么在所有核心之间平均分配问题可能会有所帮助,但是一旦它们在它们之间分开,我认为每个核心上的子问题可能是最好的用上面的算法2解决,避免进一步划分问题,当然避免递归,正如我在下面论述....
在递归的分治方法的每个递归级别,算法需要某种方式来记住问题的尚未解决的后半部分,同时它会递归到上半部分.通常,这是通过让算法首先为一半递归调用自身,然后为另一半,一种在运行时堆栈上隐式维护此信息的设计来完成的.另一种实现可以通过在显式堆栈上保持基本相同的信息来避免递归函数调用.在空间增长方面,算法2是O(1),但任何递归实现都不可避免地是O(log n),因为必须在某种堆栈上维护这些信息.但是除了空间问题之外,递归实现还有额外的运行时开销,即记住尚未递归到子问题的一半的状态,直到可以递归到它们为止.这种运行时开销并不是免费的,并且考虑到上面算法2的实现的简单性,我认为这种开销是成比例的.因此,我建议上面的算法2将对绝大多数情况下的任何递归实现进行全面打击.