使用 oh-my-zsh

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

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self

题解

求逆序数问题，可以用归并排序统计总数。

1、暴力

时间复杂度：$O(n^2)$，显然超时！！！

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        // 暴力
        int len = nums.length;
        int[] count = new int[len];
        for (int i = len - 1;i >= 0;i--) {
            count[i] = 0;
            // 存在重复计算
            for (int j = len - 1;j > i;j--) {
                if (nums[i] > nums[j]) {
                    count[i]++;
                }
            }
        }
        ArrayList<Integer> res = new ArrayList<>();
        for (int c : count) {
            res.add(c);
        }
        return res;
    }
}

2、离散化树状数组

树状数组

树状数组 是一种可以动态维护序列前缀和的数据结构，它的功能是：

• 单点更新 update(i,v)：把序列i的位置的数加上一个值v，在该题中v = 1
• 区间查询 query(i)：查询序列[1...i]区间的区间和，即i位置的前缀和

修改和查询的时间代价是$O(logn)$，其中n为需要维护前缀和的序列长度

转化成动态维护前缀和问题

前缀和counnt[i]表示：nums[i]之后小于nums[i]数量总和

离散化优化空间

• 值域映射

class Solution {
    private int[] c;
    private int[] a;

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> resultList = new ArrayList<Integer>();
        discretization(nums);
        init(nums.length + 5);
        for (int i = nums.length - 1;i >= 0;--i) {
            int id = getId(nums[i]);
            resultList.add(query(id-1));
            update(id);
        }

        Collections.reverse(resultList);
        return resultList;
    }

    // 初始化前缀和
    private void init(int length) {
        c = new int[length];
        Arrays.fill(c,0);
    }

    private int lowBit(int x) {
        // -x <==> (~x + 1)
        return x & (-x);
    }

    private void update(int pos) {
        while(pos < c.length) {
            c[pos] += 1;
            pos += lowBit(pos);
        }
    }

    private int query(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret += c[pos];
            pos -= lowBit(pos);
        }

        return ret;
    }

    private void discretization(int[] nums) {
        // hash表去重
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }

        int size = set.size();
        a = new int[size];
        int index = 0;
        for (int num : set) {
            a[index++] = num;
        }

        Arrays.sort(a);
    }

    private int getId(int x) {
        return Arrays.binarySearch(a,x) + 1;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com