企业官网建设流程全解析

【算法详解】统计下标的相反奇偶性得分（两种解法：暴力枚举+后缀统计优化）

一、题目描述

给定一个长度为n的整数数组nums，我们需要定义每个下标i的奇偶性相反得分：

下标i的分数 = 满足以下两个条件的下标j的总数量：

1. 下标范围：i \< j \< n（j 必须是 i 右侧的元素）

2. 奇偶性：nums\[i\]和nums\[j\]奇偶性不同（一奇一偶）

最终要求返回一个长度为n的结果数组answer，answer\[i\]对应下标i的得分。

1.1 示例演示

示例 1

输入：nums = [1,2,3,4]

输出：[2,1,1,0]

详细解析：

• 下标0（值1，奇数）：右侧j=1(偶数)、j=3(偶数) → 得分2

• 下标1（值2，偶数）：右侧j=2(奇数) → 得分1

• 下标2（值3，奇数）：右侧j=3(偶数) → 得分1

• 下标3（值4，偶数）：无右侧元素 → 得分0

示例 2

输入：nums = [1]

输出：[0]

解析：数组仅有一个元素，无右侧下标，得分为0。

1.2 题目约束

• 1 \<= nums\.length \<= 100

• 1 \<= nums\[i\] \<= 100

数据规模较小，暴力解法可直接通过，同时也可实现优化解法锻炼算法思维。

二、解题思路总览

针对本题，我将提供两种解题解法，由浅入深讲解：

1. 暴力枚举法：双层循环遍历所有合法的 i、j 组合，统计奇偶相反数量，思路最简单、易理解

2. 后缀统计优化法：提前预处理数组后缀的奇数、偶数数量，单层循环遍历计算结果，降低时间复杂度

三、解法一：暴力枚举法（基础解法）

3.1 算法思路

根据题目定义，直接模拟得分统计逻辑：

1. 遍历每个下标i（0 ~ n-1）

2. 针对每个 i，遍历其右侧所有下标j（i+1 ~ n-1）

3. 判断nums\[i\]和nums\[j\]奇偶性是否不同，不同则当前得分+1

4. 遍历完成后，记录当前下标得分，最终返回结果数组

奇偶性判断技巧：数字对2取余，num % 2 == 1为奇数，num % 2 == 0为偶数。两个数奇偶性不同的条件：\(nums\[i\] % 2\) \!= \(nums\[j\] % 2\)。

3.2 完整代码实现

classSolution:defcountOppositeParity(self,nums:list[int])->list[int]:# ©leetcoden=len(nums)answer=[0]*n# 遍历每个下标iforiinrange(n):# 遍历i右侧的所有下标jforjinrange(i+1,n):# 判断奇偶性是否不同if(nums[i]%2)!=(nums[j]%2):answer[i]+=1returnanswer

3.3 代码测试

# 测试案例if__name__=="__main__":sol=Solution()# 测试示例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 算法思路

暴力解法存在大量重复的奇偶判断，我们可以通过预处理后缀奇偶数量优化效率：

1. 从后往前遍历数组，提前统计每个下标i右侧所有元素中，奇数的总数量、偶数的总数量

2. 若当前nums\[i\]是奇数，则右侧所有偶数的数量就是当前下标得分

3. 若当前nums\[i\]是偶数，则右侧所有奇数的数量就是当前下标得分

4. 遍历过程中动态更新后缀奇偶总数，仅需一次遍历即可完成计算

核心逻辑：当前元素的相反奇偶后缀数量 = 当前下标得分，规避双层循环，大幅减少运算次数。

4.2 完整代码实现

classSolution:defcountOppositeParity(self,nums:list[int])->list[int]:# ©leetcoden=len(nums)answer=[0]*n# 初始化后缀奇数、偶数数量，统计当前下标右侧所有元素的奇偶个数suffix_odd=0suffix_even=0# 从倒数第二个元素向前遍历（最后一个元素无右侧元素，得分恒为0）foriinrange(n-2,-1,-1):# 先把【i+1】元素加入后缀统计（i的右侧第一个元素，属于i的后缀）next_num=nums[i+1]ifnext_num%2==1:suffix_odd+=1else:suffix_even+=1# 再计算当前i的得分current_num=nums[i]ifcurrent_num%2==1:# 当前为奇数，得分为右侧偶数总数answer[i]=suffix_evenelse:# 当前为偶数，得分为右侧奇数总数answer[i]=suffix_oddreturnanswer

4.3 代码测试

# 测试案例if__name__=="__main__":sol=Solution()# 测试示例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\]为例，分步演示执行过程：

1. 初始化：suffix_odd=0，suffix_even=0，answer=[0,0,0,0]

2. 遍历 i=2（元素3，奇数）：先加入i+1=3（元素4，偶数），suffix_even=1；当前为奇数，得分=右侧偶数数=1 → answer[2]=1

3. 遍历 i=1（元素2，偶数）：先加入i+1=2（元素3，奇数），suffix_odd=1；当前为偶数，得分=右侧奇数数=1 → answer[1]=1

4. 遍历 i=0（元素1，奇数）：先加入i+1=1（元素2，偶数），suffix_even=2；当前为奇数，得分=右侧偶数数=2 → answer[0]=2

最终得到结果 [2,1,1,0]，与题目示例标准答案完全一致。本次BUG核心原因：原代码先计算得分、再统计后缀，导致首次统计时后缀数据为空，得分计算错误；修复后先更新后缀数据、再计算得分，逻辑完全正确。

4.5 复杂度分析

• 时间复杂度：O\(n\)，仅需单次遍历数组，时间效率大幅提升

• 空间复杂度：O\(1\)，仅使用两个变量统计后缀奇偶数量，无额外数组开销

五、两种解法对比总结

六、解题核心要点

1. 奇偶性判断核心：num % 2，通过取余结果快速区分奇偶

2. 得分核心逻辑：当前元素奇数→统计右侧偶数数量，当前元素偶数→统计右侧奇数数量

3. 优化关键：避免重复遍历，通过后缀预处理将平方复杂度降为线性复杂度