跳转至

3907. 统计具有相反奇偶性的较小元素 🔒

题目描述

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

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

  • i < j < n
  • nums[j] < nums[i]
  • nums[i] 和 nums[j] 有不同的奇偶性（一个是偶数，另一个是奇数）。

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

 

示例 1：

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

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

解释：

  • 对于 i = 0，元素 nums[1] = 2 和 nums[2] = 4 更小且奇偶性不同。
  • 对于 i = 1，元素 nums[3] = 1 更小且奇偶性不同。
  • 对于 i = 2，元素 nums[3] = 1 和 nums[4] = 3 更小且奇偶性不同。
  • 剩余下标无有效元素。

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

示例 2：

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

输出：[1,1,0]

解释：

对于 i = 0 和 i = 1，元素 nums[2] = 1 更小且奇偶性不同。因此，answer = [1, 1, 0]。

示例 3：

输入：nums = [7]

输出：[0]

解释：

没有元素在下标 0 右侧，因此其得分为 0。因此，answer = [0]。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

解法

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

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

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

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
}

评论