给定一个整数数组,使用数组的数字找到LARGEST数字,使其可被3整除

Question

例如:数组:4,3,0,1,5 {假设所有数字> = 0.数组中的每个元素也对应一个数字.即数组中的每个元素都在0到9之间.}

在上面的数组中,最大的数字是:5430 {使用数组中的数字5,4,3和0}

我的方法:

对于3的可分性,我们需要数字的总和可以被3整除.所以,

1. 步骤1:从阵列中删除所有零.
2. 第2步:这些零将在最后出现.{因为他们不影响总和,我们必须找到最大的数字}
3. 步骤3:找到数组元素的子集(不包括零),使得位数为MAXIMUM,并且数字之和为MAXIMUM,总和可以被3整除.
4. 步骤4:所需数字由上面找到的数字按降序排列.

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

我在想,也许Step-3可以通过GREEDY CHOICE来完成所有元素并继续删除集合中的最小元素,直到总和可以被3整除.

但我不相信这个贪婪的选择会起作用.

请告诉我的方法是否正确.如果是,那么请建议如何做第3步？

此外,请建议任何其他可能/有效的算法.

Answer 1

观察:如果你能得到一个可被3整除的数字,你需要删除最多2个数字,以保持最佳解决方案.

一个简单的O(n^2)解决方案是检查删除1个数字的所有可能性,如果没有,则检查所有对(有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)空间-你只需要2个最小值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"

Answer 2

贪婪的选择肯定不起作用:考虑一下{5, 2, 1}.你要删除第1一个,但你应该删除2.

我认为你应该算出数组模3的总和,它是0(你已经完成),或者是1或2.然后你要去掉其模3的总和为1或2的最小子集.

我认为这很简单,所以不需要动态编程.如果可能的话,通过删除具有该模数的一个数字来执行此操作,否则通过使用其他模数移除两个数字来执 一旦知道要移除多少,请选择尽可能小的.你永远不需要删除三个数字.

您不需要0特别处理,但如果您打算这样做,那么如果您暂时从中移除所有0,3,6,9,则可以进一步减少步骤3中考虑的集合.

总而言之,我可能会:

• 对数字进行排序,降序.
• 计算模数.如果为0,我们就完成了.
• 尝试从结尾开始删除具有该模数的数字.如果成功,我们就完成了.
• 从末尾开始删除具有负模数的两位数字.这总是成功的,所以我们完成了.
• 我们可能会留下一个空数组(例如,如果是输入1, 1),在这种情况下问题是不可能的.否则,数组包含结果的数字.

O(n)提供时间复杂度,您在步骤1中进行计数排序.由于值是数字,您当然可以.