检查数组中的任何数字是否等于特定数字的最有效方法是什么，例如：（5,3,3,9,4）的数组我想知道数组中的任何这些数字是否可以添加到 10 这将在我添加 (3,3,4) 时发生
问问题
137 次
1 回答
0
我将不得不花费比现在更多的时间来提出一个非常好的解决方案，但我建议重新考虑你的策略。正如@DeepakBala 提到的，您正在描述一个 NP 完全问题。
使这一点不同的一件事是总和 (Q) 可以明显大于数组中的数字。此外，由于它们被限制在 3 到 150 之间，所以当您有 2000 个数字时，您将有很多重复。充分利用这一点 - 在使用数字之前先数好数字，您只需要担心 149 种数字。
为了让您思考为什么这很重要，请考虑将 100 万个数字按 1-100 排序。只需创建一个数组，然后计算您看到每个数字的次数。然后通过打印出每个数字适当的次数来重新创建列表。这是 O(n) 而不是正常的 O(n log(n))。
与其使用多达 2000 个数字的数组，不如考虑 150 个数组，它会告诉您每种尺寸有多少可用以及您正在使用的每种尺寸有多少。
试着把所有的大数相加，直到你得到 Q 的 150 以内，然后看看你是否有任何完美地弥补了差异。如果失败了，您将不得不弄清楚如何从那里开始。
于 2013-04-15T17:58:37.183 回答