贪心算法数字列表
贪心算法数字列表
提问于 2020-06-25 04:09:59
我在c++工作，我需要找到一个贪婪的算法，给出一个正整数数组，确定哪些对相加的偶数相等的数组的右边有一些奇数比这个和大。返回所有的可能性。我已经想过创建一个配对数字及其位置的列表，这样我就可以从这个位置跳到最后。但是这些子结构给了我答案，所以它不是一个贪婪的算法，补充说它的标准是不正确的。有人能帮我吗？
Example:
[4,5,9,4,0,11,6,6,8,8,91,73,7,69]
Output:
[4,4,11,91,73,69]
[6,6,91,73,69]
[8,8,11,91,73,69]谢谢:)
回答 1
Stack Overflow用户
发布于 2020-06-26 16:17:43
解决方案不是很整洁。如果需要的话，我希望有人能详细说明这一点。
假设给定数组中的最大数(称为A)是M。创建另一个数组BM+1并初始化Bx=-1。遍历A。如果BA[x]== -1，则将其设为x。如果不是-1且BA[x]=-1，则将BA[x] =x设为x(否则，不要干扰)。这样，您可以用A的每个元素x的前两个位置填充B。这可以在O(N)中完成。
Run a loop i through B :
if B[i][1] != -1 :
run a loop j though A from j=B[i][1]+1 :
print if A[j] > 2*i and A[j] is odd第二部分可以在O(N^2)中完成，其总复杂度(时间)为O(N^2)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62563289
复制相关文章
相似问题
腾讯云开发者
