3917. 统计下标的相反奇偶性得分

题目描述

给你一个长度为 n 的整数数组 nums。

下标 i 的分数定义为满足以下条件的下标 j 的数量：

i < j < n，并且
nums[i] 和 nums[j] 的奇偶性不同（一个为偶数，另一个为奇数）。

返回一个长度为 n 的整数数组 answer，其中 answer[i] 表示下标 i 的分数。

示例 1：

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

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

解释：

nums[0] = 1，为奇数。因此，下标 j = 1 和 j = 3 满足条件，所以下标 0 的分数为 2。
nums[1] = 2，为偶数。因此，下标 j = 2 满足条件，所以下标 1 的分数为 1。
nums[2] = 3，为奇数。因此，下标 j = 3 满足条件，所以下标 2 的分数为 1。
nums[3] = 4，为偶数。因此，没有下标满足条件，所以下标 3 的分数为 0。

因此，answer = [2, 1, 1, 0]。

示例 2：

输入： nums = [1]

输出： [0]

解释：

nums 中只有一个元素。因此，下标 0 的分数为 0。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

解法

方法一：计数

我们首先统计数组 \(\textit{nums}\) 中偶数和奇数的数量，分别记为 \(cnt[0]\) 和 \(cnt[1]\)。

然后，我们从左到右遍历数组 \(\textit{nums}\)，对于下标 \(i\)，我们先将 \(cnt[\textit{nums}[i] \bmod 2]\) 减 1，然后将 \(cnt[\textit{nums}[i] \bmod 2 \oplus 1]\) 的值赋给 \(ans[i]\)。

遍历结束后，返回答案数组 \(ans\) 即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。忽略答案数组的空间复杂度，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def countOppositeParity(self, nums: list[int]) -> list[int]:
        cnt = [0, 0]
        for x in nums:
            cnt[x & 1] += 1
        ans = [0] * len(nums)
        for i, x in enumerate(nums):
            cnt[x & 1] -= 1
            ans[i] = cnt[x & 1 ^ 1]
        return ans

class Solution {
    public int[] countOppositeParity(int[] nums) {
        int[] cnt = new int[2];
        for (int x : nums) {
            cnt[x & 1]++;
        }
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            cnt[nums[i] & 1]--;
            ans[i] = cnt[nums[i] & 1 ^ 1];
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> countOppositeParity(vector<int>& nums) {
        int cnt[2] = {0, 0};
        for (int x : nums) {
            cnt[x & 1]++;
        }
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            cnt[nums[i] & 1]--;
            ans[i] = cnt[(nums[i] & 1) ^ 1];
        }
        return ans;
    }
};

func countOppositeParity(nums []int) []int {
    cnt := [2]int{}
    for _, x := range nums {
        cnt[x&1]++
    }
    n := len(nums)
    ans := make([]int, n)
    for i, x := range nums {
        cnt[x&1]--
        ans[i] = cnt[x&1^1]
    }
    return ans
}

function countOppositeParity(nums: number[]): number[] {
    const cnt = Array<number>(2).fill(0);
    for (const x of nums) {
        ++cnt[x & 1];
    }
    const n = nums.length;
    const ans = Array<number>(n).fill(0);
    for (let i = 0; i < n; ++i) {
        --cnt[nums[i] & 1];
        ans[i] = cnt[(nums[i] & 1) ^ 1];
    }
    return ans;
}

3917. 统计下标的相反奇偶性得分

题目描述

解法

方法一：计数

评论