难度: Medium
Submission
运行时间: 70 ms
内存: 27.9 MB
class Solution:
def largestEvenSum(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = -1
# 选取k次，获得最大偶数和
# 排序取逆序
# 排序后如果最大的k项总和本身就是偶数，则合法
# 如果是总和是奇数
# 则抛弃k个中最小的奇数，用不在其中的最大的偶数替换。
# 或者抛弃k个中最小的偶数，用不在其中的最大奇数替换
# 两者取总和更大的
nums.sort(reverse=True)
tSum = sum(nums[:k])
if tSum%2 == 0:
return tSum
else:
# 情况1:抛弃k个中最小的奇数，用不在其中的最大的偶数替换。
p1 = k-1
while p1 >= 0 and nums[p1]%2 == 0:
p1 -= 1
p2 = k
while p2 < n and nums[p2]%2 == 1:
p2 += 1
if p1 >= 0 and p2 < n and nums[p1]%2 == 1 and nums[p2]%2 == 0: # 说明找到了
ans = max(ans,tSum-abs(nums[p2]-nums[p1]))
## 情况2：抛弃k个中最小的偶数，用不在其中的最大奇数替换
p3 = k-1
while p3 >= 0 and nums[p3]%2 == 1:
p3 -= 1
p4 = k
while p4 < n and nums[p4]%2 == 0:
p4 += 1
if p3 >= 0 and p4 < n and nums[p3]%2 == 0 and nums[p4]%2 == 1: # 说明找到了
ans = max(ans,tSum-abs(nums[p4]-nums[p3]))
return ans
Explain
本题的目标是从数组中选择K个元素，形成最大的偶数和。首先对数组进行排序并取前K个最大值进行求和。如果此和为偶数，直接返回；如果为奇数，则尝试通过替换操作得到偶数和。具体方法是：将K个中最小的奇数替换为剩余元素中最大的偶数，或将K个中最小的偶数替换为剩余元素中最大的奇数，两种情况分别计算可能的最大偶数和，取其最大值。
时间复杂度: O(n log n)
空间复杂度: O(1)
class Solution:
def largestEvenSum(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = -1
nums.sort(reverse=True) # 对数组进行降序排序
tSum = sum(nums[:k]) # 计算前K大元素的和
if tSum % 2 == 0: # 如果和为偶数，直接返回
return tSum
else:
p1 = k-1
while p1 >= 0 and nums[p1] % 2 == 0: # 找出K个元素中最小的奇数
p1 -= 1
p2 = k
while p2 < n and nums[p2] % 2 == 1: # 找出剩余元素中最大的偶数
p2 += 1
if p1 >= 0 and p2 < n and nums[p1] % 2 == 1 and nums[p2] % 2 == 0:
ans = max(ans, tSum - abs(nums[p2] - nums[p1])) # 尝试替换，计算可能的最大偶数和
p3 = k-1
while p3 >= 0 and nums[p3] % 2 == 1: # 找出K个元素中最小的偶数
p3 -= 1
p4 = k
while p4 < n and nums[p4] % 2 == 0: # 找出剩余元素中最大的奇数
p4 += 1
if p3 >= 0 and p4 < n and nums[p3] % 2 == 0 and nums[p4] % 2 == 1:
ans = max(ans, tSum - abs(nums[p4] - nums[p3])) # 尝试另一种替换，计算可能的最大偶数和
return ans # 返回最大偶数和
Explore
因为题目的目标是求得一个最大的偶数和。如果求得的和已经是偶数，那么这就是符合条件的答案，无需进一步处理。如果和是奇数，那么就需要通过某种方式（如替换操作）调整以使总和变为偶数，从而满足题目要求。
这里使用`abs(nums[p2] - nums[p1])`可能是题解中的笔误。实际上，应该是检查替换后的和是否为偶数，以及替换后的和是否比当前最大偶数和要大。正确的操作是直接替换，然后重新计算总和。这里的目标是通过替换来确保总和为偶数的同时，尽可能地大。
如果无法在K个最大元素中找到合适的替换奇数或偶数，或在剩余元素中找不到适合的替换对象，这意味着无法通过替换操作形成偶数和。在这种情况下，如果已有的和是奇数，则无法形成偶数和，应返回-1或其他标志值，表示无法达到题目要求的结果。
尽管替换策略旨在最大化偶数和，但这种方法不一定总能保证得到最大可能的偶数和。这是因为可能存在多种替换组合，而算法可能只检查了一部分。例如，可能需要一种更复杂的查找或优化策略来确保在所有可能的替换中找到确实能得到最大偶数和的那一种。因此，当前的策略是一种贪心方法，虽然在很多情况下有效，但不保证总是最优。