LeetCode奇偶数组构造：数学性质与贪心算法解析

1. 题目解析与数学本质挖掘

这道LeetCode题目编号为[题目编号]，表面上看是一个数组构造问题，实际上考察的是对数学奇偶性性质的深刻理解。我们先完整复现题目要求：

给定一个长度为n的数组nums1，其中所有元素互不相同。需要构造另一个数组nums2满足：

1. nums2所有元素必须全为奇数或全为偶数（奇偶一致性）
2. 对于每个位置i，可以选择：
   • 直接取nums1[i]
   • 或者取nums1[i]±1（即相邻整数）

关键提示：题目中±1操作的成本是相同的，这暗示我们不需要考虑操作次数最小化，只需要关注奇偶性转换的可能性。

1.1 奇偶运算的基本性质

解决这个问题的核心在于理解奇偶数的运算规律：

• 偶数 ± 偶数 = 偶数
• 奇数 ± 奇数 = 偶数
• 偶数 ± 奇数 = 奇数
• 奇数 ± 偶数 = 奇数

特别地，对于±1操作：

• 奇数 ±1 → 偶数
• 偶数 ±1 → 奇数

这意味着我们可以通过±1操作在奇偶性之间自由切换。

1.2 问题转化与关键结论

基于上述性质，我们可以得出以下结论：

1. 如果原数组已经是全奇数或全偶数，直接返回原数组即可
2. 如果原数组同时包含奇数和偶数：
   • 可以通过±1操作将所有数转为奇数
   • 也可以通过±1操作将所有数转为偶数
   • 但无法同时满足两种方案（因为原始奇偶性不同）

因此，这个问题的解总是存在，我们只需要判断原数组是否已经满足奇偶一致性即可。

2. 贪心算法设计与实现

2.1 算法思路

基于数学分析，我们可以设计出极简算法：

1. 统计原数组中奇数和偶数的数量
2. 如果全为奇数或全为偶数 → 直接返回原数组
3. 否则 → 可以通过±1操作统一为全奇或全偶数组

实际上，我们甚至不需要真正构造nums2数组，只需要验证是否存在构造可能性即可。

2.2 Python实现代码

python复制def isPossible(nums):
    has_odd = any(x % 2 == 1 for x in nums)
    has_even = any(x % 2 == 0 for x in nums)
    
    # 情况1：已经是全奇或全偶
    if not (