【算法详解】统计下标的相反奇偶性得分两种解法暴力枚举后缀统计优化一、题目描述给定一个长度为n的整数数组nums我们需要定义每个下标i的奇偶性相反得分下标i的分数 满足以下两个条件的下标j的总数量下标范围i \lt; j \lt; nj 必须是 i 右侧的元素奇偶性nums\[i\]和nums\[j\]奇偶性不同一奇一偶最终要求返回一个长度为n的结果数组answeranswer\[i\]对应下标i的得分。1.1 示例演示示例 1输入nums [1,2,3,4]输出[2,1,1,0]详细解析下标0值1奇数右侧j1(偶数)、j3(偶数) → 得分2下标1值2偶数右侧j2(奇数) → 得分1下标2值3奇数右侧j3(偶数) → 得分1下标3值4偶数无右侧元素 → 得分0示例 2输入nums [1]输出[0]解析数组仅有一个元素无右侧下标得分为0。1.2 题目约束1 \lt; nums\.length \lt; 1001 \lt; nums\[i\] \lt; 100数据规模较小暴力解法可直接通过同时也可实现优化解法锻炼算法思维。二、解题思路总览针对本题我将提供两种解题解法由浅入深讲解暴力枚举法双层循环遍历所有合法的 i、j 组合统计奇偶相反数量思路最简单、易理解后缀统计优化法提前预处理数组后缀的奇数、偶数数量单层循环遍历计算结果降低时间复杂度三、解法一暴力枚举法基础解法3.1 算法思路根据题目定义直接模拟得分统计逻辑遍历每个下标i0 ~ n-1针对每个 i遍历其右侧所有下标ji1 ~ n-1判断nums\[i\]和nums\[j\]奇偶性是否不同不同则当前得分1遍历完成后记录当前下标得分最终返回结果数组奇偶性判断技巧数字对2取余num % 2 1为奇数num % 2 0为偶数。两个数奇偶性不同的条件\(nums\[i\] % 2\) \! \(nums\[j\] % 2\)。3.2 完整代码实现classSolution:defcountOppositeParity(self,nums:list[int])-list[int]:# ©leetcodenlen(nums)answer[0]*n# 遍历每个下标iforiinrange(n):# 遍历i右侧的所有下标jforjinrange(i1,n):# 判断奇偶性是否不同if(nums[i]%2)!(nums[j]%2):answer[i]1returnanswer3.3 代码测试# 测试案例if__name____main__:solSolution()# 测试示例1print(sol.countOppositeParity([1,2,3,4]))# 输出 [2,1,1,0]# 测试示例2print(sol.countOppositeParity([1]))# 输出 [0]# 额外测试案例print(sol.countOppositeParity([2,4,6,7]))# 输出 [1,1,1,0]3.4 复杂度分析时间复杂度O\(n²\)n 为数组长度双层循环遍历所有 i、j 组合最坏循环 n*(n-1)/2 次空间复杂度O\(1\)仅使用常数额外空间结果数组为题目要求输出不计入额外空间由于题目数据规模 n≤100最大循环次数仅 4950 次暴力解法完全满足题目要求。四、解法二后缀统计优化法进阶优化4.1 算法思路暴力解法存在大量重复的奇偶判断我们可以通过预处理后缀奇偶数量优化效率从后往前遍历数组提前统计每个下标i右侧所有元素中奇数的总数量、偶数的总数量若当前nums\[i\]是奇数则右侧所有偶数的数量就是当前下标得分若当前nums\[i\]是偶数则右侧所有奇数的数量就是当前下标得分遍历过程中动态更新后缀奇偶总数仅需一次遍历即可完成计算核心逻辑当前元素的相反奇偶后缀数量 当前下标得分规避双层循环大幅减少运算次数。4.2 完整代码实现classSolution:defcountOppositeParity(self,nums:list[int])-list[int]:# ©leetcodenlen(nums)answer[0]*n# 初始化后缀奇数、偶数数量统计当前下标右侧所有元素的奇偶个数suffix_odd0suffix_even0# 从倒数第二个元素向前遍历最后一个元素无右侧元素得分恒为0foriinrange(n-2,-1,-1):# 先把【i1】元素加入后缀统计i的右侧第一个元素属于i的后缀next_numnums[i1]ifnext_num%21:suffix_odd1else:suffix_even1# 再计算当前i的得分current_numnums[i]ifcurrent_num%21:# 当前为奇数得分为右侧偶数总数answer[i]suffix_evenelse:# 当前为偶数得分为右侧奇数总数answer[i]suffix_oddreturnanswer4.3 代码测试# 测试案例if__name____main__:solSolution()# 测试示例1print(sol.countOppositeParity([1,2,3,4]))# 输出 [2,1,1,0]# 测试示例2print(sol.countOppositeParity([1]))# 输出 [0]# 额外测试案例print(sol.countOppositeParity([2,3,5,8]))# 输出 [2,1,1,0]print(sol.countOppositeParity([3,5,7,9]))# 输出 [0,0,0,0]4.4 分步逻辑解析以输入nums \[1,2,3,4\]为例分步演示执行过程初始化suffix_odd0suffix_even0answer[0,0,0,0]遍历 i2元素3奇数先加入i13元素4偶数suffix_even1当前为奇数得分右侧偶数数1 → answer[2]1遍历 i1元素2偶数先加入i12元素3奇数suffix_odd1当前为偶数得分右侧奇数数1 → answer[1]1遍历 i0元素1奇数先加入i11元素2偶数suffix_even2当前为奇数得分右侧偶数数2 → answer[0]2最终得到结果 [2,1,1,0]与题目示例标准答案完全一致。本次BUG核心原因原代码先计算得分、再统计后缀导致首次统计时后缀数据为空得分计算错误修复后先更新后缀数据、再计算得分逻辑完全正确。4.5 复杂度分析时间复杂度O\(n\)仅需单次遍历数组时间效率大幅提升空间复杂度O\(1\)仅使用两个变量统计后缀奇偶数量无额外数组开销五、两种解法对比总结解法时间复杂度空间复杂度优点缺点暴力枚举法O(n²)O(1)逻辑直观、代码简洁、零思维成本适合新手数据量大时效率低后缀统计优化法O(n)O(1)时间效率最优适配大规模数据需要理解后缀遍历逻辑思维稍复杂六、解题核心要点奇偶性判断核心num % 2通过取余结果快速区分奇偶得分核心逻辑当前元素奇数→统计右侧偶数数量当前元素偶数→统计右侧奇数数量优化关键避免重复遍历通过后缀预处理将平方复杂度降为线性复杂度