LeetCode 315. 计算右侧小于当前元素的个数

Categories:

题目描述
思路分析
1. 解法一：树状数组 + 离散化（推荐）
相似题目

题目描述

✅ 315. 计算右侧小于当前元素的个数

思路分析

解法一：树状数组 + 离散化（推荐）

核心思路：

先对所有数值排序去重，得到离散化后的索引。

从右往左遍历数组，查询比当前值小的计数并更新当前值。

树状数组支持前缀和查询与单点更新。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数组长度。

空间复杂度：O(n)，树状数组与离散化数组。

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);

        Map<Integer, Integer> index = new HashMap<>();
        int id = 1;
        for (int v : sorted) {
            if (!index.containsKey(v)) {
                index.put(v, id++);
            }
        }

        int[] bit = new int[id + 2];
        List<Integer> ans = new ArrayList<>(n);

        // 从右往左统计
        for (int i = n - 1; i >= 0; i--) {
            int pos = index.get(nums[i]);
            ans.add(query(bit, pos - 1));
            add(bit, pos, 1);
        }

        Collections.reverse(ans);
        return ans;
    }

    private void add(int[] bit, int i, int delta) {
        while (i < bit.length) {
            bit[i] += delta;
            i += i & -i;
        }
    }

    private int query(int[] bit, int i) {
        int sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i & -i;
        }
        return sum;
    }
}

import "sort"

func countSmaller(nums []int) []int {
    n := len(nums)
    sorted := append([]int(nil), nums...)
    sort.Ints(sorted)

    index := make(map[int]int, n)
    id := 1
    for _, v := range sorted {
        if _, ok := index[v]; !ok {
            index[v] = id
            id++
        }
    }

    bit := make([]int, id+2)
    ans := make([]int, 0, n)

    // 从右往左统计
    for i := n - 1; i >= 0; i-- {
        pos := index[nums[i]]
        ans = append(ans, query(bit, pos-1))
        add(bit, pos, 1)
    }

    for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
        ans[i], ans[j] = ans[j], ans[i]
    }

    return ans
}

func add(bit []int, i int, delta int) {
    for i < len(bit) {
        bit[i] += delta
        i += i & -i
    }
}

func query(bit []int, i int) int {
    sum := 0
    for i > 0 {
        sum += bit[i]
        i -= i & -i
    }
    return sum
}

相似题目

题目	难度	考察点
327. 区间和的个数	困难	树状数组
493. 翻转对	困难	归并/树状数组
1649. 通过指令创建有序数组	困难	树状数组
300. 最长递增子序列	中等	二分
307. 区域和检索 - 数组可修改	中等	树状数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/56290699