gpt4 book ai didi

algorithm - Find the min Facebook 黑客杯 2013

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:14:57 24 4
gpt4 key购买 nike

<分区>

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

这里是问题: Find the min Facebook Hacker Cup 2013

这是我找到这个问题的解决方案的网站: Solutions

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

Although these first K values could be anything, we can make some useful observationsabout the contents of the array after the initial K elements:

  1. Every element will be between 0 and K (inclusive) by the pigeonhole principle.
  2. Consequently, every window of K + 1 consecutive elements will contain each value between 0 and K exactly once (i.e. it contains a permutation of the integers 0 through K).
  3. Consequently, for 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 个的元素。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com