3

既然比赛已经结束了，我想问一下这个问题。在过去的三天里，我一直在为这个问题苦苦挣扎，因为实际上我无法理解它。

问题来了： 找到 2013 年 Facebook 黑客杯的最低人数

这是我为这个问题找到解决方案的网站： 解决方案

我无法理解的是以下部分：

尽管这些前 K 值可以是任何值，但我们可以对初始 K 元素之后的数组内容进行一些有用的观察：

  1. 根据鸽巢原理，每个元素都在 0 和 K（含）之间。
  2. 因此，K + 1 个连续元素的每个窗口将包含 0 到 K 之间的每个值恰好一次（即它包含整数 0 到 K 的排列）。
  3. 因此，对于 i > 2K：M[i] = M[i - (K + 1)]。

虽然如果第一点是真的，我能够理解第二点和第三点。第一个真的让我很困扰。为什么元素必须在 0 和 K 之间，为什么它们不能都是初始 K 元素中不存在的最小非负整数。

例如：对于以下测试用例：

1

46 18

7 11 9 46

前 K 个元素是：

[7、40、35、26、19、34、15、36、37、2、31、28、41、0、9、16、1、20]

现在为什么其余元素必须在 0 到 18 之间，而我之前的 K 个元素中有超过 18 个的元素。

4

1 回答 1

3

假设你有 K 个数字{a0,a1,a2...a(k-1)}，现在你想找到第一个不在其中的非负数。能超过K吗？好吧，如果这是真的，那么所有数字{0,1,...K}都存在于上述集合中，即K+1数字应该存在于上述由K数字组成的集合中。这是不可能的，并且与新数字大于 的假设相矛盾K。因此，在每个步骤中，您添加的下一个数字将在该范围内[0,K]，因此在该K+1步骤上，所有最后一个K+1数字都将在该步骤中，因此在该范围内是不同的数字。

于 2013-01-29T14:26:53.843 回答