数组中的所有元素都是排序和不同的,但它们不一定是整数类型(即它们可能是浮点类型).
解决方法
问题没有说明[]的排序顺序,这是一个非常重要的缺失信息.如果它是递增的,最坏情况下的复杂性将始终为O(n),我们无法做任何事情来使最坏情况的复杂性更好.但是如果排序顺序是下降的,即使是最坏情况的复杂性也是O(log n)：因为数组中的值是不同的并且是降序的,所以只有一个可能的索引,其中a [i]可以等于i,基本上所有你要做的是二元搜索以找到交叉点(如果有这样的交叉,则升序索引值越过降序元素值),并确定交叉点索引值处的[c] == c C.由于这非常简单,我将继续假设排序顺序为升序.有趣的是,如果元素是整数,即使在升序的情况下也存在类似的“交叉”情况(尽管在升序的情况下可能存在多个a [i] == i匹配),所以如果元素是整数,二进制搜索也适用于升序情况,在这种情况下,即使是最坏情况的性能也是O(log n)(见Interview question – Search in sorted array X for index i such that X[i] = i).但是在这个版本的问题上我们没有给予豪华.
以下是我们如何解决此问题：
从第一个元素开始,a [0].如果它的值是== 0,你找到了一个满足[i] == i的元素,所以返回true.如果它的值是< 1,下一个元素(a [1])可能包含值1,因此您将继续下一个索引.但是,如果[0]> = 1,你知道(因为值是不同的)条件a [1] == 1不可能是真的,所以你可以安全地跳过索引1.但你甚至可以做比这更好：例如,如果a [0] == 12,你知道(因为值按升序排序),在元素a之前不可能有任何满足[i] == i的元素[13 ].因为数组中的值可以是非整数的,所以我们不能在此处进行任何进一步的假设,因此我们可以安全地直接跳到的下一个元素是[13](例如a [1]到[12]可能全部包含12.000 ...和13.000之间的值......这样[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)
}
如果[]中的许多值大于它们的索引值,那么它具有相当好的性能,并且如果[]中的所有值都大于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来说是最坏的情况.在第一次分割之后,我们可以检查两半的顶部和顶部.对于相同极端情况的底部元素,其导致算法2的O(1)性能,但是在两个半部合并的情况下导致O(n)性能.如果下半部分中的所有元素都小于0并且上半部分中的所有元素都大于n-1,则会出现这种情况.在这些情况下,对于我们可以排除的任何一半,我们可以立即将O(1)性能排除在底部和/或上半部分之外.当然,在进一步递归之后仍然需要确定该测试不能排除的任何一半的性能,再将该半除以半直到我们找到其顶部或底部元素包含其索引值的任何段.与算法2相比,这是一个相当不错的性能提升,但它仅出现在算法2最坏情况的某些特殊情况下.我们用分而治之的方式做的就是减少(略微)引起最坏情况行为的问题空间的比例.对于分而治之,仍然存在最坏情况,它们完全匹配大多数问题空间,这会引发算法2的最坏情况行为.
因此,鉴于分而治之的算法具有较少的最坏情况,继续使用分而治之的方法是不是有意义？
总之,没有.也许.如果您事先知道大约一半的数据小于0且一半大于n,那么这种特殊情况通常会采用分而治之的方法.或者,如果您的系统是多核的并且您的’n’很大,那么在所有核心之间平均分配问题可能会有所帮助,但是一旦它们在它们之间分开,我认为每个核心上的子问题可能是最好的用上面的算法2解决,避免进一步划分问题,当然避免递归,正如我在下面论述….
在递归的分治方法的每个递归级别,算法需要某种方式来记住问题的尚未解决的后半部分,同时它会递归到上半部分.通常,这是通过让算法首先为一半递归调用自身,然后为另一半,一种在运行时堆栈上隐式维护此信息的设计来完成的.另一种实现可以通过在显式堆栈上保持基本相同的信息来避免递归函数调用.在空间增长方面,算法2是O(1),但任何递归实现都不可避免地是O(log n),因为必须在某种堆栈上维护这些信息.但是除了空间问题之外,递归实现还有额外的运行时开销,即记住尚未递归到子问题的一半的状态,直到可以递归到它们为止.这种运行时开销并不是免费的,并且考虑到上面算法2的实现的简单性,我认为这种开销是成比例的.因此,我建议上面的算法2将对绝大多数情况下的任何递归实现进行全面打击.
