2026-07-11构造奇偶一致的数组Ⅱ。用go语言给定一个长度为 n 的整数数组 nums1所有元素互不相同。需要构造一个同样长度为 n 的数组 nums2使得 nums2 的每个元素都必须是奇数或者都必须是偶数只能二选一。对每个下标 inums2[i] 只能用两种方式之一生成要么直接取 nums2[i] 等于 nums1[i]要么选择某个不同下标 j把 nums2[i] 设为 nums1[i] 减去 nums1[j]并且要求这个差值为正即 nums1[i] - nums1[j] 1。如果能找到某种构造使得 nums2 全为奇数或全为偶数则返回 true否则返回 false。1 n nums1.length 100000。1 nums1[i] 1000000000。nums1 中的所有整数互不相同。输入 nums1 [1,4,7]。输出 true。解释​​​​​​​​​​​​​​设置 nums2[0] nums1[0] 1。设置 nums2[1] nums1[1] - nums1[0] 4 - 1 3。设置 nums2[2] nums1[2] 7。nums2 [1, 3, 7]所有元素均为奇数。因此答案为 true。题目来自力扣3876。一、先拆解题目核心规则与奇偶数学基础1. nums2 元素生成规则每个位置二选一对任意下标 i方案Anums2[i] nums1[i]直接复用原数方案B找另一个下标 jj≠i满足nums1[i] - nums1[j] ≥ 1令nums2[i] nums1[i] - nums1[j]最终要求整个 nums2全部奇数 或 全部偶数满足其一就返回 true。2. 奇偶加减基础规律解题核心设 a、b 为整数奇数 − 奇数 偶数偶数 − 偶数 偶数奇数 − 偶数 奇数偶数 − 奇数 奇数结论两数做差奇偶性由两数是否相同决定相同奇偶得偶不同奇偶得奇。3. 目标拆解只分两种可行目标满足任一即true目标1构造全奇数 nums2目标2构造全偶数 nums2只要其中一种目标存在可行构造答案就是 true。二、分步推导代码的完整逻辑对应 uniformArray 函数思路步骤1遍历数组记录全局最小奇数、全局最小偶数初始化两个极值变量mn[0]存最小偶数、mn[1]存最小奇数初始值设为系统最大整数代表当前还没找到对应类型数字逐个遍历 nums1 中每个数字 x用x 1判断奇偶结果0偶数、结果1奇数把当前类型的最小值更新如果x比已存的同类型最小值更小就替换遍历结束后得到两个关键值mn[0]数组里所有偶数的最小值若无偶数保持最大值mn[1]数组里所有奇数的最小值若无奇数保持最大值。步骤2分类讨论数组本身的奇偶构成判断是否能构造合法nums2情况A数组只有偶数mn[1] 极大值没有奇数此时直接满足函数返回条件mn[1] math.MaxInt直接返回 true。原理每个位置i都选择方案A直接取原偶数nums2 全偶数天然合法。情况B数组只有奇数mn[0] 极大值没有偶数此时mn[0] mn[1]恒成立极大值一定大于奇数最小值满足第二个判断条件返回 true。原理每个位置i直接取原奇数nums2 全奇数天然合法。情况C数组同时存在奇数、偶数mn[0]、mn[1]都不是极大值此时判断条件最小偶数 最小奇数mn[0] mn[1]分两种子情况子情况C1最小偶数 最小奇数 → 返回true以示例[1,4,7]举例最小奇数 mn[1]1最小偶数 mn[0]441符合条件。推导为什么能构造全奇数nums2全局最小数字是奇数最小奇数记为 min_odd对数组里任意数字 x分两类处理若x本身是奇数直接方案Anums2[i]x天然奇数若x是偶数x 一定大于 min_odd全局最小数是奇数所有偶数都比它大满足x - min_odd ≥ 1根据奇偶规律偶数−奇数奇数因此选方案B用j对应min_odd的下标差值就是奇数所有位置都能生成奇数nums2全奇数符合要求。子情况C2最小偶数 最小奇数 → 返回false此时全局最小数字是偶数 min_even数组同时有奇数、偶数无法构造全奇数/全偶数数组尝试构造全奇数nums2数组里存在奇数奇数只能通过两种方式变成奇数①直接保留奇数②奇数−偶数。但全局最小数是偶数 min_even所有奇数都大于 min_even奇数减min_even确实是奇数但数组里的偶数无法变成奇数偶数要得到奇数只能 偶数−奇数但所有奇数都比min_even大而当前最小偶数比所有奇数更小不存在任何奇数满足「偶数−奇数≥1」偶数位置无法生成奇数全奇数方案作废。尝试构造全偶数nums2奇数想要生成偶数只能用「奇数−奇数」但全局最小数字是偶数不存在比奇数更小的奇数任意奇数找不到j满足差值为正且同为奇数奇数位置无法生成偶数全偶数方案作废。两种目标都无法实现最终返回 false。步骤3整合判断逻辑统一返回结果函数判断式mn[1] math.MaxInt || mn[0] mn[1]等价于要么数组无奇数全偶数直接合法要么最小偶数大于最小奇数可以构造全奇数数组满足任意一条就返回true其余情况返回false。三、示例 [1,4,7] 完整演算过程遍历数组提取奇偶最小值x1奇数mn[1]更新为1x4偶数mn[0]更新为4x7奇数mn[1]仍为1状态mn[0]4mn[1]1两种数字都存在判断 4 1条件成立返回true实操构造nums2下标0数字1奇数直接保留得1下标1数字4偶数减去全局最小奇数14-13奇数下标2数字7奇数直接保留得7nums2[1,3,7]全部奇数符合题目要求。四、时间复杂度、额外空间复杂度分析1. 时间复杂度核心操作单次完整遍历数组 nums1数组长度为 n遍历内每个元素仅做奇偶判断、一次最小值比较均为 O(1) 常量操作无嵌套循环、无排序、无哈希、无额外多次遍历总时间复杂度O(n)n 为数组长度上限1e5效率满足题目数据范围。2. 额外空间复杂度仅开辟固定长度数组mn [2]int只存储两个整数空间大小与输入数组长度 n 无关属于常量空间没有开辟动态切片、哈希表、辅助数组等随n增长的空间总额外空间复杂度O(1)常数空间。Go完整代码如下packagemainimport(fmtmath)funcuniformArray(nums1[]int)bool{// 计算最小偶数、最小奇数mn:[2]int{math.MaxInt,math.MaxInt}for_,x:rangenums1{mn[x1]min(mn[x1],x)// 1 比 %2 好nums1 有负数也适用}// 只有偶数或者偶数 最小的偶数 最小的奇数// 只有奇数的情况蕴含在 mn[0] mn[1] 中returnmn[1]math.MaxInt||mn[0]mn[1]}funcmain(){nums1:[]int{1,4,7}result:uniformArray(nums1)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathfromtypingimportListdefuniform_array(nums:List[int])-bool:# 计算最小偶数、最小奇数mn[math.inf,math.inf]forxinnums:# 1 比 % 2 更好nums 有负数也适用mn[x1]min(mn[x1],x)# 只有偶数或者偶数 最小的偶数 最小的奇数# 只有奇数的情况蕴含在 mn[0] mn[1] 中returnmn[1]math.informn[0]mn[1]defmain():nums[1,4,7]resultuniform_array(nums)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includeclimits#includealgorithmbooluniformArray(conststd::vectorintnums){// 计算最小偶数、最小奇数intmn[2]{INT_MAX,INT_MAX};for(intx:nums){// 1 比 % 2 更好nums 有负数也适用mn[x1]std::min(mn[x1],x);}// 只有偶数或者偶数 最小的偶数 最小的奇数// 只有奇数的情况蕴含在 mn[0] mn[1] 中returnmn[1]INT_MAX||mn[0]mn[1];}intmain(){std::vectorintnums{1,4,7};boolresultuniformArray(nums);std::coutstd::boolalpharesultstd::endl;return0;}