Kth最小元素和Kth元素？

Question

我真的很困惑Kth最小元素和Kth元素之间到底有什么区别。

第k个元素=第k个元素是数组=数组[k-1]

但是，什么是第k个最小元素？我有一个家庭作业问题，我需要写一个算法来找到2个排序数组中的第k个最小元素。我不是来要求你做作业的，你不需要给我任何算法或代码。我只想理解它是什么意思。Kth最小元素和kth元素之间有什么不同。

我问这个问题的原因是：我在谷歌上搜索什么是第k个最小的元素，其中一个是：

For example if A = [10, 20, 40, 60] and B =[15, 35, 50, 70, 100] and K = 4 
then solution should be 35 because union of above arrays will be C = 
[10,15,20,35,40,50,60,70,100] and fourth smallest element is 35.

它与数组的第k个元素完全相同。答案是UB[k-1]。

另一个例子是：

A = [3, 5, 9, 15, 27, 33, 35, 41, 57, 65]
B = [1, 16, 18, 42, 44, 46, 48, 50, 52, 54]

AUB = [1, 3, 5, 9, 15, 16, 18, 27, 33, 35, 41, 42, 44, 46, 48, 50, 52, 54, 57, 65]
and if k = 6
then AUB[6-1] = 16;
if k = 8
then AUB[8-1] = 27;

我说得对吗？kth最小元素不在AUB[k-1]是否有例外？如果是，你能给我举个例子，并解释一下吗？

编辑：我刚刚看到有人说第k个最小的元素是按升序排列的数组[k-1]。

我问老师一个问题：

当我们谈论第k个元素时，它是在[k]还是[k-1]

他的回答是：

仔细阅读问题陈述。输出应该是S U T中2n个元素中第k个最小的元素。输出不一定在任何一个列表的索引k处。为什么会这样？

我不明白。输出不一定在两个列表的索引k处？这意味着什么？

Answer 1

两个数组的并集就是一个包含两个数组的所有元素的数组。

例如A[1,20,40,70]和B[10,50,60,80]上述两个数组的并集可以是C[1,20,40,70,10,50,60,80]

现在假设k的范围从1开始（包括1），假设k=3，现在第k个元素是40，但第k个最小元素是20。

有效地做到这一点的方法取决于你如何做到这一点。一种（不太有效）的方法可能是简单地使用k个嵌套迭代，并从未排序的联合数组中找到第k个最小元素。

另一种方法可能是在取并集后对数组进行排序，另一种方法是简单地合并两个数组，这样就可以对结果并集进行排序（合并排序：合并过程）。在这种情况下，生成的数组将具有与第k个元素相同的第k个最小元素。

Answer 2

输出不一定在两个列表的索引k处？这意味着什么？

这意味着您应该在不创建C的情况下解决问题，也就是AUB。

相反，您应该并行迭代两个数组，直到找到第k个最小的元素。

伪逻辑：

Ai = 0, Bi = 0
Loop K-1 times:
    if A[Ai] < B[Bi] then Ai++ else Bi++
kth smallest = min(A[Ai], B[Bi])

实例

A = [10, 20, 40, 60], B =[15, 35, 50, 70, 100], K = 4

Ai = 0, Bi = 0: A[0] < B[0] so Ai++
Ai = 1, Bi = 0: A[1] > B[0] so Bi++
Ai = 1, Bi = 1: A[1] < B[1] so Ai++
Ai = 2, Bi = 1: min(A[2], B[1]) = 35

第四个最小值是35，位于B[1]。

如您所见，输出不在任何列表的索引3（=4-1）。

Kth最小元素和Kth元素？

因为你从不创建一个组合列表，而是直接在两个不同的列表上工作，所以没有第k个元素，所以标题中提出的问题是没有意义的。

Answer 3

正如您已经指出的，这两个数组的并集将是您要查看的内容。下面是一个例子：

S = [0,4,5,7]
T = [1,2,8,9]
then A = S v T = [0,1,2,4,5,7,8,9]

现在，当你查看这个数组时，你会发现第k个元素位于索引k-1。这是因为我们倾向于从一开始计算。所以我们说第一个元素，我们指的是索引0处的元素。

接下来，这也是你另一个问题的答案。因为你有两个数组，第k个最小的数字将在A[k-1]，但是你的老师的意思是在任何一个数组中，所以S和T它们可能不在indexk-1。在上面的例子中，第5个最小的数字是5在index4ofA，但是它是S或S[2]中的第三个元素。