假设您有一个数字集/列表/集合:[1,3,7,13,21,19](顺序无关紧要)。假设出于不重要的原因，您通过一个函数运行它们并收到以下对: (1, 13), (1, 19), (1, 21), (3,19), (7, 3), (7,13), (7,19), (21, 13), (21 ,19).同样，顺序无关紧要。我的问题涉及下一部分:如何找出可以成为一对而不重复的数字的最小数量？对于这个特定的序列，它是全部六个。对于 [1,4,2]，对是 (1,4)、(1,2)、(2,4)。在这种情况下，可以排除任何一个数字，因为它们都是成对的，但它们每个都重复，因此它将是 2(哪个 2 无关紧要)。 乍一看，这似乎是一个图遍历问题——数字是节点，对边。是否有数学的某些部分处理这个问题？我写遍历算法没问题，我只是想知道是否有时间复杂度较低的解决方案。谢谢!
最佳答案
如果您真的想要找到最小数量，答案是 0，因为您根本不必使用任何数字。
我猜你是想写“最大数量的数字”。
如果我对您的问题的理解正确，听起来我们可以将其转化为以下问题: 给定一组 n 个数字 (1,..,n)，我可以使用多少个数字来将这组数字分成对，其中每个数字只能出现一次。
这个问题的答案是:
- 当 n = 2k f(n) = 2k 对于 k>=0
- 当 n = 2k+1 f(n) = 2k 对于 k>=0
我将使用归纳法进行解释。
- 如果 n = 0 那么我们最多可以使用 0 个数字来创建对。
- 如果 n = 2(集合可以是 [1,2])那么我们可以使用这两个数字来 创建一对 (1,2)
- 假设:如果 n=2k 让我们假设我们可以使用所有 2k 个数字来创建 2k 对并使用归纳法证明我们可以使用 2k+2 个数字来满足 n = 2k+2。
- 证明:如果 n = 2k+2, [1,2,..,k,..,2k,2k+1,2k+2]，我们可以使用 2k 个数字(根据我们的假设)创建 k 对。不失一般性，假设输出对是 (1,2),(3,4),..,(2k-1,2k)。我们可以看到我们还有两个数字 [2k+1, 2k+2] 我们没有使用，因此我们可以从其中两个中创建一对，这意味着我们使用了 2k+2 个数字。<
当n为奇数时，你可以自行证明。
关于python - 图遍历，也许是另一种数学？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52231442/