python获取具有k个元素的数组的最大偶数和

Question

我一直在研究python算法，想解决一个问题:

1. 给定一个正整数数组A和一个整数K。
2. 找出数组 A 与 K 个元素的最大偶数和。
3. 如果不可能，返回-1。

例如，如果有一个数组 A= [1,2,3,4,4,5] 且 K= 3， 答案是12(5+4+3)， 这是具有 K(3) 个元素的最大偶数和。 但是，如果 A= [3, 3, 3] 且 K= 1， 答案是 -1，因为它不能与一个元素求和。

我试图从数组中排除每个最小奇数，但是当 while 循环中 K=n 时它失败了。 有什么简单的方法可以解决这个问题吗？如果您能提供一些建议，我将不胜感激。

Answer 1

对数组进行排序并“取”最大的 K 个元素。

如果它已经是偶数 - 你就完成了。

否则，您需要恰好替换一个元素，用您没有选择的奇数元素替换您选择的偶数元素，或者相反。您需要将两个元素之间的差异最小化。

天真的解决方案将检查所有可能的方法来做到这一点，但那是 O(n^2)。通过检查实际的两个可行候选者，您可以做得更好:

• 你没有选择的最大奇数元素，以及最小的 甚至你选择的元素
• 你没有选择的最大偶数元素和你选择的最小奇数元素。

选择两个元素之间的差异最小的那个。如果不存在这样的两个元素(即您的 k=3, [3,3,3] 示例)- 没有可行的解决方案。

排序的时间复杂度是O(nlogn)。

在我的(非常生锈的)python 中，它应该是这样的:

def FindMaximalEvenArray(a, k):
    a = sorted(a)
    chosen = a[len(a)-k:]
    not_chosen = a[0:len(a)-k]
    
    if sum(chosen) % 2 == 0:
        return sum(chosen)
    
    smallest_chosen_even = next((x for x in chosen if x % 2 == 0), None)
    biggest_not_chosen_odd = next((x for x in not_chosen[::-1] if x % 2 != 0), None)    
    candidiate1 = smallest_chosen_even - biggest_not_chosen_odd  if smallest_chosen_even and biggest_not_chosen_odd else float("inf")

    smallest_chosen_odd = next((x for x in chosen if x % 2 != 0), None)
    biggest_not_chosen_even = next((x for x in not_chosen[::-1] if x % 2 == 0), None)
    candidiate2 = smallest_chosen_odd - biggest_not_chosen_even  if smallest_chosen_odd and biggest_not_chosen_even else float("inf")

    if candidiate1 == float("inf") and candidiate2 == float("inf"):
        return -1
    return sum(chosen) - min(candidiate1, candidiate2)

注意:这可以做得更好(在时间复杂度方面)，因为你实际上并不关心所有元素的顺序，只关心“候选者”和前 K 个元素。因此，您可以使用选择算法而不是排序，这将使它在 O(n) 时间内运行。