LeetCode 构造奇偶一致数组｜数学奇偶性推导+贪心极简解法（Python逐行精讲）

LeetCode 构造奇偶一致数组数学奇偶性推导贪心极简解法Python逐行精讲题目难度中等核心考点数学奇偶性性质、贪心算法、逻辑简化适用人群算法初学者、秋招春招刷题、数学思维类题型练习这道题看似是数组构造类模拟题实则是纯数学奇偶性问题无需暴力枚举所有构造可能抓住奇数、偶数加减运算的奇偶不变性就能把复杂的构造逻辑简化为一行判断彻底规避超时和冗余代码属于典型的“数学秒杀算法题”。一、题目原题复现与核心解读1.1 题目完整描述给你一个长度为n的数组nums1其中包含互不相同的整数。你需要构造另一个长度相同的数组nums2满足nums2内所有元素全为奇数或全为偶数奇偶完全一致每个下标i必须二选一nums2[i] nums1[i]直接取原数nums2[i] nums1[i] - nums1[j]j≠i做差值运算如果能构造出符合要求的nums2返回True否则返回False。1.2 关键示例演示示例1输入nums1 [2,3] 输出true 解释 nums2[0] 2-3 -1奇数 nums2[1] 3奇数 最终nums2 [-1,3]全奇满足条件示例2输入nums1 [4,6] 输出true 解释 直接取原数nums2 [4,6]全偶满足条件1.3 题目隐藏约束与误区提醒数组元素互不相同但不影响奇偶性判断无需考虑重复值差值可正可负正负不改变奇偶性-1和1同为奇数-4和4同为偶数不需要实际构造出nums2只需要判断能否构造核心是数学推导而非模拟二、核心数学原理奇偶性不变性解题关键这道题的突破口完全在奇数和偶数的加减运算规律我们先梳理核心奇偶性规则这是后续算法的底层逻辑偶数 ± 偶数 偶数奇数 ± 奇数 偶数偶数 ± 奇数 奇数结合题目中的两种取值方式推导单个元素的奇偶性变化规律核心结论1. 若直接取原数nums1[i]奇偶性完全不变2. 若取差值nums1[i]-nums1[j]最终奇偶性 nums1[i]奇偶性XORnums1[j]奇偶性3.只要数组中同时存在奇数和偶数一定能构造出全奇数组4. 若数组全为偶数/全为奇数直接返回True直接取原数即可。2.1 结论推导假设数组里既有奇数又有偶数- 对奇数元素直接保留保持奇数- 对偶数元素用“偶数 - 奇数”结果为奇数即可将偶数转为奇数最终所有元素都能变为奇数必然满足条件。只有一种极端情况需要特殊考虑吗不存在只要不是单一奇偶就一定可行单一奇偶直接可行。最终极简判断逻辑统计数组中奇数的个数和偶数的个数- 全奇 / 全偶 → return True- 既有奇又有偶 → return True也就是说这道题永远返回True结合题目约束元素互不相同n≥1所有测试用例最终结果都是True三、完整代码实现严格贴合指定格式按照题目要求的代码格式编写代码极简注释详尽可直接提交LeetCode时间复杂度O(n)空间复杂度O(1)最优解。classSolution:defuniformArray(self,nums1:list[int])-bool:# ©leetcode# 统计数组中奇数的数量odd_count0fornuminnums1:ifnum%2!0:odd_count1# 情况1全偶数奇数个数为0→ 直接返回True# 情况2全奇数奇数个数数组长度→ 直接返回True# 情况3既有奇数又有偶数 → 可构造全奇数组返回TruereturnTrue3.1 代码逐行精讲类与方法定义严格遵循题目指定格式class Solutiondef uniformArray参数和返回值类型完全匹配奇数计数遍历数组统计奇数个数用于验证奇偶分布逻辑严谨直接返回True通过前文数学推导所有合法输入都能构造出目标数组无返回False的场景3.2 精简版代码一行写法classSolution:defuniformArray(self,nums1:list[int])-bool:# ©leetcode# 数学推导所有情况均可行returnTrue四、测试用例全覆盖验证我们针对各类边界情况和常规用例测试确保代码正确性输入nums1奇偶分布输出结果验证说明[2,3]一奇一偶True可构造全奇数组匹配示例1[4,6]全偶True直接取原数全偶数组匹配示例2[1,3,5]全奇True直接取原数全奇数组[5]单个奇数True单个元素天然满足条件[2,5,7,8]奇偶混合True偶数转奇数最终全奇五、算法复杂度分析5.1 时间复杂度O(n)n为数组长度仅需一次遍历统计奇数个数精简版为O(1)无循环嵌套、无递归效率拉满完全适配题目n≤100的约束。5.2 空间复杂度O(1)仅使用常数个临时变量无额外数组、哈希表等空间开销属于原地算法。六、解题思路总结与误区避坑6.1 核心解题思路摒弃模拟构造的暴力思路抓住奇偶性运算不变性这一核心数学规律推导得出所有输入都能构造出符合要求的奇偶一致数组直接返回True即可代码严格遵循题目格式兼顾可读性和极简性6.2 常见误区误区1强行模拟构造nums2写大量分支判断代码冗余且易出错误区2忽略正负不影响奇偶性纠结差值的正负问题误区3误以为存在返回False的情况实则题目约束下无此场景这道题是典型的数学思维优先于代码实现的算法题刷题时切忌一上来就写模拟代码先分析题目背后的数学规律往往能找到秒杀解法。