algorithm - 修剪和搜索算法有困难

Question

在第 4 步之前我确实理解输入(如果我的理解是正确的)但是第 5 步有点困惑，因为我不知道我应该在 |S₁| 中输入什么+ |S₂| ≥ k -- 我什至不确定它是绝对值还是什么。我也没有得到迭代。嗯嗯

Answer 1

所以在第 4 步之后:

• S1包含小于p的元素
• S2 包含 p 的多次出现且仅包含 p 的出现
• S3包含大于p的元素

因此

• 如果|S1| > k 然后它包含 S 的第 k 个元素
• 否则如果|S1| + |S2| > k 然后 S2 包含 S 的第 k 个元素，因此是 p
• else S3中S中的第k个元素。所以搜索 s 的第 k 个元素与搜索 S3 的 (k-|S1|-|S2|) 元素是一样的。因此，您使用 S = S3 和 k=k-|S1|-|S2| 重新启动(即迭代)相同的算法。

希望这对您有所帮助。