Find the k th smallest element in the union of 2 sorted lists of size m and n
在两个大小为m和n的有序列表的联合中找到第k个最小的元素
with efficiency log(k) ,, i have done a lot of thinking and searching i also got the
由于效率日志(k)，我做了很多思考和搜索，我也得到了。
pesedocode and the explain to it ... so far i still doesn't get or understand the
pesedocode和解释…到目前为止，我还没有得到或理解。
the question right .. any help will be appreciated....
问题. .任何帮助将不胜感激....
1 个解决方案
#1
5
So you have to sets, say { 1, 4, 5, 7, 8, 12, 98, 1993 } and { 2, 5, 8, 10, 88 }. And you want to find the third smallest element.
所以你必须设置，比如{1,4,5,7,8,12,98,1993}和{2,5,8,10,88}。你想要找到第三个最小的元素。
That means m=8, n=5, and k=3. Visually inspecting these sets, you'll see that the answer is 4. Your finding algorithm has to find the correct value within O(log(k)) (that's "big O").
这意味着m=8 n=5, k=3。查看这些集合，您将看到答案是4。您的查找算法必须在O(log(k))中找到正确的值(即“大O”)。
That means if your algorithm finds the element with a number of steps N = n1 + n2 + ..., where each of n1, n2, ... is a function of k, the rate of growth of all of n1, n2... must be less than or equal to the rate of growth of log(k).
这意味着，如果你的算法找到的元素有很多步骤N = n1 + n2 +…， n1, n2，…是k的函数，所有n1 n2的增长率。必须小于或等于log(k)的生长速率。
If that doesn't make sense, aim to find the element in less than k steps (where k > 1).
如果没有意义，目标是在k步以下找到元素(k > 1)。
#1
5
So you have to sets, say { 1, 4, 5, 7, 8, 12, 98, 1993 } and { 2, 5, 8, 10, 88 }. And you want to find the third smallest element.
所以你必须设置，比如{1,4,5,7,8,12,98,1993}和{2,5,8,10,88}。你想要找到第三个最小的元素。
That means m=8, n=5, and k=3. Visually inspecting these sets, you'll see that the answer is 4. Your finding algorithm has to find the correct value within O(log(k)) (that's "big O").
这意味着m=8 n=5, k=3。查看这些集合，您将看到答案是4。您的查找算法必须在O(log(k))中找到正确的值(即“大O”)。
That means if your algorithm finds the element with a number of steps N = n1 + n2 + ..., where each of n1, n2, ... is a function of k, the rate of growth of all of n1, n2... must be less than or equal to the rate of growth of log(k).
这意味着，如果你的算法找到的元素有很多步骤N = n1 + n2 +…， n1, n2，…是k的函数，所有n1 n2的增长率。必须小于或等于log(k)的生长速率。
If that doesn't make sense, aim to find the element in less than k steps (where k > 1).
如果没有意义，目标是在k步以下找到元素(k > 1)。