查找的大小为m和2名排序的列表Ñ找到第k个最小的元素在联合的2排序的大小为m列表和n与效率日志(k)的
与工会第k个最小的元素效率日志(K),,我已经做了很多思考和寻找我也得到了
pesedocode和解释吧......到目前为止,我还没有得到或理解
问题对..任何帮助将不胜感激....
查找的大小为m和2名排序的列表Ñ找到第k个最小的元素在联合的2排序的大小为m列表和n与效率日志(k)的
与工会第k个最小的元素效率日志(K),,我已经做了很多思考和寻找我也得到了
pesedocode和解释吧......到目前为止,我还没有得到或理解
问题对..任何帮助将不胜感激....
所以你必须设置,比如说{ 1, 4, 5, 7, 8, 12, 98, 1993 }
和{ 2, 5, 8, 10, 88 }
。 而你想找到第三小元素。
这意味着m = 8,n = 5和k = 3。 通过目视检查这些设置,您将看到答案是4. 您的查找算法必须在O(log(k))
(即“大O”)内找到正确的值。
这意味着,如果您的算法找到该元件具有多个步骤N = n1 + n2 + ...
,其中每个的n1, n2, ...
是k的函数,所有的n1, n2...
的生长速率必须小于或等于日志的生长速率(K)。
如果这没有意义,目标是找到少于k步骤(其中k> 1)的元素。
+1:对问题的清晰解释 – 2010-11-16 21:13:55
+1:很好完成 – pstrjds 2010-11-16 21:16:50
你的解释很安静,但我想关注的是如果我们考虑k = 3时如何得到4的部分?我对此有点困惑......所以我很感谢任何澄清 – 2010-11-18 09:55:46
请概述你到目前为止。我不认为有人想为你做功课。 :-) – dawg 2010-11-16 21:01:11
如果你有什么特别不明白的地方,可以询问一下。如果没有,请展示您目前的工作,但无论您身在何处,我们都应该能够帮助您重新开始工作。 – 2010-11-16 21:05:12
@drewk:他说他不明白这个问题。他没有要求答案。 – Brendan 2010-11-16 21:11:34