c++ - 贪心算法编号 list

Question

我在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]

谢谢 :)

Answer 1

解决方案不是很整洁。我希望有人可以详细说明这一点。
假定给定数组(称为A)中的最大数字为M。创建另一个数组B [M + 1] [2]，然后初始化B [x] [y] =-1。遍历A。如果B [A [x]] [0] ==-1，则使其为x。如果它不是-1并且B [A [x]] [1] =-1，则使B [A [x]] [1] = 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)的总复杂度(时间)。