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

数组中的所有元素都是排序和不同的,但它们不一定是整数类型(即它们可能是浮点类型).

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

问题没有说明[]的排序顺序,这是一个非常重要的缺失信息.如果它是递增的,最坏情况下的复杂性将始终为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将对绝大多数情况下的任何递归实现进行全面打击.

仅供参考：随机==伪随机

A.当生成均匀随机数时,我可以指定一个范围,即：

(Math.random()-Math.random())*10+5
//generates numbers between -5 and 15

B.使用高斯式正态随机性版本生成一组随机值：

//pass in the mean and standard deviation
function randomnorm(mean,stdev) {
  return Math.round((Math.random()*2-1)+(Math.random()*2-1)+(Math.random()*2-1))*stdev+mean);
}

//using the following values:
{
  mean:400,standard_deviation:1
  //results in a range of 397-403,or +-range of 3
},{
  mean:400,standard_deviation:10
  //results in a range of 372-429,or +-range of 30
},standard_deviation:25
  //results in a range of 326-471,or +-range of 75
}

每一个给我一系列近似standard_deviation *( – 3)(假设我让程序运行时间更长).

C.我可以按如下方式计算这个范围：

>假设我想要一个范围从300-500,所以var total_range = 200;
>我的意思是400,我的范围是total_range / 2(var r = 100)
>因此standard_deviation为r / 3或在本例中为33.333.

这似乎有效,但我不知道我在做什么数学所以我觉得自己像个白痴,这个解决方案感觉很笨拙而且不完全准确.

我的问题：
我有什么公式可以帮助我在这里跳舞吗？我的要求如下：

>必须能够准确定义一系列数字.
>必须尽可能高效地在JavaScript中完成.

我想也许我很接近,但它并不存在.

减去两个随机数并不能给出正态分布,它会给出在零两边线性下降的数字.请参阅此小提琴中的红色图表：

http://jsfiddle.net/Guffa/tvt5K/

要获得正态分布的良好近似,请将六个随机数加在一起.请参阅小提琴中的绿色图表.

因此,要获得正态分布的随机数,请使用：

((Math.random() + Math.random() + Math.random() + Math.random() + Math.random() + Math.random()) - 3) / 3

该方法基于中心极限定理,在此作为第二种方法概述：http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_from_normal_distribution

我正在开发一个大型网站的移动版本.移动设备不需要整个网站上的大量内容.

隐藏这个的最佳方法是什么？
即什么会导致浏览器的工作量最少,所以它会保持响应？

> CSS显示：无
> jQuery的.remove()方法,例如(未经测试)：

var elements_to_remove = [
  '#sidebar','#footer','#etc'
];

$.each(elements_to_remove,function() {      
  if ($(this).length > 0) {
    $(this).remove();
  }
});

我可以看到.remove()的优点是实际上从DOM树中删除了元素,从而减少了内存使用量.

对于jQuery路由,在document.ready之前有没有更好的事件要挂钩？ (即在制作DOM树时).

另外,有关如何基准测试的任何建议？

更新：提供自定义移动版本不是一种选择,它应该与现有内容/ ‘responsive’一起使用.

最有效的方法是首先不要在页面上包含内容.

移动用户会感谢您不要使用未在页面上显示的元素浪费他们的数据资费,如果他们不需要JavaScript以便正确查看页面,他们会很高兴.