3907. Count Smaller Elements With Opposite Parity 🔒

题目描述

You are given an integer array nums of length n.

The score of an index i is defined as the number of indices j such that:

i < j < n
nums[j] < nums[i]
nums[i] and nums[j] have different parity (one is even and the other is odd).

Return an integer array answer of length n, where answer[i] is the score of index i.

Example 1:

Input: nums = [5,2,4,1,3]

Output: [2,1,2,0,0]

Explanation:

For i = 0, the elements nums[1] = 2 and nums[2] = 4 are smaller and have different parity.
For i = 1, the element nums[3] = 1 is smaller and has different parity.
For i = 2, the elements nums[3] = 1 and nums[4] = 3 are smaller and have different parity.
No valid elements exist for the remaining indices.

Thus, the answer = [2, 1, 2, 0, 0].

Example 2:

Input: nums = [4,4,1]

Output: [1,1,0]

Explanation:

For i = 0 and i = 1, the element nums[2] = 1 is smaller and has different parity. Thus, the answer = [1, 1, 0].

Example 3:

Input: nums = [7]

Output: [0]

Explanation:

No elements exist to the right of index 0, so its score is 0. Thus, the answer = [0].

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

解法

方法一：有序列表或树状数组

我们可以使用两个有序列表（或树状数组）分别维护偶数和奇数的元素。对于每个元素，我们查询另一个列表中比它小的元素的数量，并将当前元素添加到对应的列表中。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组的长度。

Python3JavaC++GoTypeScript

class Solution:
    def countSmallerOppositeParity(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [0] * n
        sl = [SortedList(), SortedList()]
        for i in range(n - 1, -1, -1):
            ans[i] = sl[nums[i] & 1 ^ 1].bisect_left(nums[i])
            sl[nums[i] & 1].add(nums[i])
        return ans

class BinaryIndexedTree {
    int n;
    int[] c;

    BinaryIndexedTree(int n) {
        this.n = n;
        this.c = new int[n + 1];
    }

    void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
}

class Solution {
    public int[] countSmallerOppositeParity(int[] nums) {
        int n = nums.length;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int m = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || sorted[i] != sorted[i - 1]) {
                sorted[m++] = sorted[i];
            }
        }
        BinaryIndexedTree[] bit = {new BinaryIndexedTree(m), new BinaryIndexedTree(m)};
        int[] ans = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            int x = Arrays.binarySearch(sorted, 0, m, nums[i]) + 1;
            ans[i] = bit[nums[i] & 1 ^ 1].query(x - 1);
            bit[nums[i] & 1].update(x, 1);
        }
        return ans;
    }
}

struct BIT {
    int n;
    vector<int> c;
    BIT(int n)
        : n(n)
        , c(n + 1, 0) {}
    void update(int x, int delta) {
        for (; x <= n; x += x & -x) c[x] += delta;
    }
    int query(int x) {
        int s = 0;
        for (; x > 0; x -= x & -x) s += c[x];
        return s;
    }
};

class Solution {
public:
    vector<int> countSmallerOppositeParity(vector<int>& nums) {
        int n = nums.size();
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

        int m = sorted.size();
        BIT* bits[2] = {new BIT(m), new BIT(m)};
        vector<int> ans(n);

        for (int i = n - 1; i >= 0; --i) {
            int x = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() + 1;
            ans[i] = bits[nums[i] & 1 ^ 1]->query(x - 1);
            bits[nums[i] & 1]->update(x, 1);
        }
        return ans;
    }
};

type BIT struct {
    n int
    c []int
}

func newBIT(n int) *BIT {
    return &BIT{n: n, c: make([]int, n+1)}
}

func (b *BIT) update(x, delta int) {
    for ; x <= b.n; x += x & -x {
        b.c[x] += delta
    }
}

func (b *BIT) query(x int) int {
    s := 0
    for ; x > 0; x -= x & -x {
        s += b.c[x]
    }
    return s
}

func countSmallerOppositeParity(nums []int) []int {
    n := len(nums)
    sorted := make([]int, n)
    copy(sorted, nums)
    sort.Ints(sorted)

    m := 0
    if n > 0 {
        m = 1
        for i := 1; i < n; i++ {
            if sorted[i] != sorted[i-1] {
                sorted[m] = sorted[i]
                m++
            }
        }
        sorted = sorted[:m]
    }

    bits := []*BIT{newBIT(m), newBIT(m)}
    ans := make([]int, n)

    for i := n - 1; i >= 0; i-- {
        x := sort.SearchInts(sorted, nums[i]) + 1
        ans[i] = bits[nums[i]&1^1].query(x - 1)
        bits[nums[i]&1].update(x, 1)
    }
    return ans
}

class BIT {
    private c: Int32Array;
    constructor(private n: number) {
        this.c = new Int32Array(n + 1);
    }
    update(x: number, delta: number) {
        for (; x <= this.n; x += x & -x) this.c[x] += delta;
    }
    query(x: number): number {
        let s = 0;
        for (; x > 0; x -= x & -x) s += this.c[x];
        return s;
    }
}

function countSmallerOppositeParity(nums: number[]): number[] {
    const n = nums.length;
    const sorted = _.sortedUniq(_.sortBy(nums));
    const m = sorted.length;

    const bits = [new BIT(m), new BIT(m)];
    const ans = new Array(n);

    for (let i = n - 1; i >= 0; i--) {
        const rank = _.sortedIndex(sorted, nums[i]) + 1;
        ans[i] = bits[(nums[i] & 1) ^ 1].query(rank - 1);
        bits[nums[i] & 1].update(rank, 1);
    }
    return ans;
}

3907. Count Smaller Elements With Opposite Parity 🔒

题目描述

解法

方法一：有序列表或树状数组

评论