这是一个家庭作业问题,但我错过了讲课,讲课的人解释了解决方法,但我还是想不出来…
如果在区间[0,1]中给n个实数(即x1,x2,x3,…,xn),则表明存在一个在最坏情况下线性时间下运行的算法,该算法给出这些n个数的排列,使得相邻数的差之和小于2。给出的提示是“buckets”。
最佳答案
好吧,你可以走这条路。将[0, 1]
分成k
段:[0, 1/k)
,[1/k, 2/k)
,…,[(k-1)/k, 1]
。
你现在浏览你的列表,首先把所有符合第一段的数字放入一个新的列表,而不是那些符合第二段的数字等等。这可以在一次通过中完成,所以O(n)
。
现在想想需要多少钱。同一区段内的个数之差最多为1/k
,即这种差异的个数n-(k-1)
。其余的(n-1)
差异是来自相邻bucket的数字之间的差异(这清楚吗,为什么?)不超过1
。总和受(n-k+1)/k + (k-1)/k
约束。如果足够小,则可以使k
足够大。
更多细节:
让我们把差异画成两种颜色:同一段数字之间的差异画成蓝色,不同段数字之间的差异画成红色。多亏了订货,我们在第一段中只有数字(可能是0),而在第二段中只有数字,以此类推。所以,我们首先有一些蓝色的差异,比红色的差异,比蓝色的差异,比红色的差异等等。
让我们看看红色差异的数量是多少。明显的红色差异不超过,对吧因为每一个红色的差异从一个片段跳到一个更高的片段。其余的区别是蓝色的。
现在,每个蓝色的差异不超过k-1
,因为minutend和subtrahend来自同一段。所有的红色差异(也就是它们的总和!)不要超过1。(暂时跳过剩下的部分,因为这是一个家庭作业问题。)
更正:
所有红色差异之和不超过2-2/k。这是为什么好吧,让我看看在最坏的情况下,第一个红色差异可能是从某段1/k
的开始到另一段A
的结束。第二种是从B
开始到其他部分B
结束的最坏情况因此,除第一段和最后一段外,每段的差异之和最多计算两次。