给定一个整数数组，使用数组中的数字找到最大的可以被3整除的数字。

Question

例如：数组：4,3,0,1,5 {假设所有数字都大于等于0。数组中的每个元素对应一个数字（即数组中的每个元素都介于0和9之间）。}

在上述数组中，最大的数字是：5430 {使用来自数组的5、4、3和0位数字}

我的方法：

要想被3整除，需要数字的总和被3整除。 所以，

1.步骤1：从数组中删除所有零。 2.步骤2：这些零将出现在末尾。{因为它们不影响总和，并且我们必须找到最大的数字} 3.步骤3：找到数组元素的子集（不包括零），使得数字的数量是最大的，数字的总和也是最大的，并且数字总和可以被3整除。 4.STEP-4：所需的数字由上面找到的集合中的数字按降序排列组成。

因此，主要步骤是STEP-3，即如何找到子集，使其包含MAX可能数量的元素，使它们的总和是MAX并且可被3整除。

我在考虑，也许可以通过贪心选择来完成Step-3，即取所有元素并继续删除集合中最小的元素，直到总和能够被3整除。

但我不确定这种贪心选择是否可行。

请告诉我我的方法是否正确。 如果是，请建议如何完成步骤3？

此外，请提出任何可能/有效的算法。

- user1599964

---

那么暴力生成所有可能性呢？也就是生成所有可以被3整除的组合，然后取最大值？ - ClemKeirua

第三步有点类似于子集和问题，但它看起来更容易（因此它可能在多项式时间内解决）。但我怀疑贪心算法在这里行不通。 - amit

@ClemKeirua：是的，蛮力法总是一个选项。但我在想是否有更有效的方法可以做到。 - user1599964

这是我的想法： 你删除零，它们将如你所说添加在末尾。 N个非零数字保留。 然后，您生成所有最大长度N的可能性。如果找到了什么，就取最大值。也许按降序排序数字可以更快。 如果找不到任何东西，您将寻找所有长度为N-1的可能性，以此类推，直到找到为止。 - ClemKeirua

顺便问一下，您没有告诉我们算法应该运行多快，数字集合有多大，您是否有这些信息？ - ClemKeirua

Answer 1

观察：如果你能得到一个可以被3整除的数字，那么你最多需要删除两个数字，才能保持最优解。

一个简单的 O(n^2) 解法是检查所有可能删除一个数字的情况，如果没有有效解，则检查所有数对（这里有O(n^2)种可能）。

---

编辑:
O(n) 解法：创建 3 个桶 - bucket1、bucket2 和 bucket0。每个桶表示数字的模 3 值。在下一个算法中忽略 bucket0。

设数组的总和为 sum。

If sum % 3 ==0: we are done.
else if sum % 3 == 1:
  if there is a number in bucket1 - chose the minimal
  else: take 2 minimals from bucket 2
else if sum % 3 == 2
  if there is a number in bucket2 - chose the minimal
  else: take 2 minimals from bucket1  

注意：为了实现 O(1) 的空间复杂度，您实际上不需要桶(bucket)，只需要从 bucket1 和 bucket2 中获取两个最小值即可，因为这是我们实际上从这些桶中使用的唯一数字。

示例：

arr = { 3, 4, 0, 1, 5 }
bucket0 = {3,0} ; bucket1 = {4,1} bucket2 = { 5 }
sum = 13 ; sum %3 = 1
bucket1 is not empty - chose minimal from it (1), and remove it from the array.
result array = { 3, 4, 0, 5 } 
proceed to STEP 4 "as planned"

- amit

---

我没有完全理解你的O(n^2)方法。你说先检查所有可能性以删除一个数字，这很好。但之后呢？如何通过检查成对关系来得出答案？ - user1599964

@user1599964：如果您无法通过删除3个数字得到一个可被3整除的数字，则最多需要删除2个数字，否则根本无法得到。 - amit

@user1599964：利用上述观察，可以得到一个O(n)的解决方案。我在编辑中添加了它。 - amit

太好了！简单高效！谢谢！你和史蒂夫的答案一样..再次感谢！ - user1599964

两点：你可以在O(n)时间内完成，而且你最多只需要删除一个点（除了极端情况）。请看下面我的答案。 - ElKamina

Answer 2

贪心策略肯定行不通：考虑集合{5, 2, 1}，你会先移除1，但你应该移除2。

我认为你应该计算数组模3的总和，结果可能是0（已完成），1或2。然后你要移除模3余数为1或2的最小子集。

我认为这很简单，所以不需要动态规划。如果可能的话，请通过删除具有该模数的一个数字来完成此操作，否则请通过删除具有另一种模数的两个数字来完成此操作。一旦你知道需要删除多少个数字，就选择最小可能的数字。你永远不需要移除三个数字。

你不需要特别对待0，尽管如果你要这样做，在第3步中可以将其临时从集合中移除所有0、3、6、9以进一步减少考虑的集合数量。

将所有内容整合在一起，我可能会：

• 按降序排序数字。
• 计算模数。如果为0，则已完成。
• 尝试从末尾开始移除具有该模数的数字。如果成功，则已完成。
• 从末尾开始移除具有负该模数的两个数字。这始终成功，因此我们已经完成了。
• 我们可能会剩下一个空数组（例如，如果输入为1,1，则问题是无法解决的）。否则，该数组包含结果的数字。

时间复杂度为O(n)，假设你在步骤1中进行计数排序。这肯定可以做到，因为值是数字。

- Steve Jessop

---

太好了！你和阿米特的解决方案完全相同。感谢你提供如此简单而又出色的算法！ - user1599964

是的，当阿米特在编辑他的时候，我正在写我的。唯一的区别是他通过取模将它们分成三个桶，而我是一个数学家，所以我数不到3，我只是把它们都放在一个数组里;-) - Steve Jessop

Answer 3

你对这个有什么看法：

首先按值对数组元素进行排序。

sum up all numbers
- if sum's remainder after division by 3 is equal to 0, just return the sorted
  array
- otherwise
    - if sum of remainders after division by 3 of all the numbers is smaller
      than the remainder of their sum, there is no solution
    - otherwise
        - if it's equal to 1, try to return the smallest number with remainder
          equal to 1, or if no such, try two smallest with remainder equal to 2,
          if no such two (I suppose it can happen), there's no solution
        - if it's equal to 2, try to return the smallest number with remainder
          equal to 2, or if no such, try two smallest with remainder equal to 1,
          if no such two, there's no solution

首先按照元素除以3的余数升序排序数组元素， 然后将每个相同余数的子集按值降序排序

- Krzysztof Jabłoński

---

太好了！似乎这3个解决方案都一样...简单而且高效！ - user1599964

Answer 4

首先，这个问题可以简化为选择最多的元素，使它们的和能够被3整除。

显然：选择所有能被3整除的数字（0、3、6、9）。

设a是余数为1的元素，b是余数为2的元素。如果(|a|-|b|)%3等于0，则从a和b中选择所有元素。如果(|a|-|b|)%3等于1，则从b中选择所有元素，并从a中选择|a|-1个最大的数字。如果余数为2，则从a中选择所有数字，并从b中选择|b|-1个最大的数字。

一旦你有了所有的数字，按照相反的顺序排序并连接起来，这就是你的答案。

最终，如果n是元素的数量，这个算法返回的数字至少有n-1位（除了特殊情况，请参见下文）。

注意：要注意特殊情况（例如，|a|=0或|b|=0等）。(-1)%3 = 2，(-2)%3 = 1。

如果m是字母表的大小，n是元素的数量，那么我的算法的时间复杂度是O(m+n)。

- ElKamina

Answer 5

排序数据是不必要的，因为只有十个不同的值。如果给定n个数字，则在O(n)内计算零、一、二等数字的数量。计算所有数字的总和，检查余数模3是否为0、1或2。

如果余数为1：删除以下的第一个可行项（其中一个保证可行）：1、4、7、2+2、2+5、5+5、2+8、5+8、8+8。

如果余数为2：删除以下第一个可能的项（其中一个保证可行）：2、5、8、1+1、1+4、4+4、1+7、4+7、7+7。

如果没有剩余数字，则问题无法解决。否则，解决方案将由连接9、8、7等数字所组成，直到没有数字为止。（对n个数字进行排序需要O(n log n)。除非您按照每个数字出现的频率进行排序，并根据这些数字生成排序后的结果）。

- gnasher729

Answer 6

Amit的答案有一个小问题。

如果bucket1不为空，但它的值非常大，比如79和97，而b2也不为空，它的2个最小值是2和5。那么在这种情况下，当所有数字的模数为1时，我们应该选择从bucket 2中删除2和5，而不是从bucket 1中删除最小值，以获得最大的连接数。

测试用例：8 2 3 5 78 79

如果我们按照Amit和Steve建议的方法，最大的数字将是878532，而在此数组中可能被3整除的最大数字是879783。

解决方案是将适当的bucket的最小最小值与另一个bucket的两个最小值的连接进行比较，并消除较小的那个。

- Awijit Gupta