题目分析

在前面刚刚讲解完逆序对，下面就来了一题类似的题目，这个题目比逆序对稍微又困难了一点，暴力算法肯定是不能做出来了，还是两种方法，分治算法和树状数组，小伙伴们尝试一下如何求解，有困难的小伙伴可以参考逆序对

分治算法

本题难度比逆序对难度大的原因在于，逆序对在对子问题求解完毕后，可以改变数组的位置，而本题因为要记录某个元素右边小于当前元素的个数，如果位置发生变化，则需要对应到原来的索引。

比如例题中的[5, 2, 6, 1]，在对子问题[5, 2]和[6, 1]求解时，得到5右边是1，6右边也是1，因此结果为[1, 0, 1, 0]，然后会将子数组进行排序，数组变为[2, 5, 1, 6]，然后归并时，2右边是1，但是2对应的索引不是0，而是1，因此不能对索引0加1，而是应该对索引1加1。因此需要找一个映射relfectIndex，记录着当前元素对应原来的索引位置。

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int[] index = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res.add(0);
            index[i] = i;
        }
        merge(nums, 0, nums.length - 1, res, index);
        return res;
    }

    private void merge(int[] nums, int left, int right, List<Integer> res, int[] index) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >> 1;
        merge(nums, left, mid, res, index);
        merge(nums, mid + 1, right, res, index);

        int leftPtr = left;
        int rightPtr = mid + 1;
        while (leftPtr <= mid) {
            while (rightPtr <= right && nums[leftPtr] > nums[rightPtr]) {
                rightPtr++;
            }
            res.set(index[leftPtr], res.get(index[leftPtr]) + rightPtr - mid - 1);
            leftPtr++;
        }

        leftPtr = left;
        rightPtr = mid + 1;
        int[] reflectIndex = new int[right - left + 1];
        for (int i = 0; i < reflectIndex.length; i++) {
            reflectIndex[i] = index[left + i];
        }
        int[] reflectArray = new int[right - left + 1];
        int idx = 0;
        while (leftPtr <= mid && rightPtr <= right) {
            if (nums[leftPtr] < nums[rightPtr]) {
                reflectArray[idx] = nums[leftPtr];
                index[left + idx] = reflectIndex[leftPtr - left];
                idx++;
                leftPtr++;
            } else {
                reflectArray[idx] = nums[rightPtr];
                index[left + idx] = reflectIndex[rightPtr - left];
                idx++;
                rightPtr++;
            }
        }
        while (leftPtr <= mid) {
            reflectArray[idx] = nums[leftPtr];
            index[left + idx] = reflectIndex[leftPtr - left];
            idx++;
            leftPtr++;
        }
        while (rightPtr <= right) {
            reflectArray[idx] = nums[rightPtr];
            index[left + idx] = reflectIndex[rightPtr - left];
            idx++;
            rightPtr++;
        }
        for (int i = 0; i < reflectArray.length; i++) {
            nums[left + i] = reflectArray[i];
        }
    }
}

树状数组

树状数组求解此题是最简单的，和逆序对一样。树状数组求解逆序对的方法，就是求解每一个元素后面有多少元素小于该元素，并结果相加。现在不需要相加，把结果加到数组里即可。

因为树状数组求解本题是从后向前遍历的，因此要进行头插法，而返回值是一个List，因此创建链表实现的LinkedList是最优的数据结构。

class Solution {
    private HashMap<Integer, Integer> reflect;

    private int[] tree;

    public List<Integer> countSmaller(int[] nums) {
        getReflect(nums);
        LinkedList<Integer> res = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int reflectVal = reflect.get(nums[i]);
            res.addFirst(query(reflectVal - 1));
            add(reflectVal);
        }
        return res;
    }

    private void getReflect(int[] nums) {
        HashSet<Integer> set = new HashSet<>(nums.length);
        for (int x : nums) {
            set.add(x);
        }
        int[] tmp = new int[set.size()];
        int idx = 0;
        for (int x: set) {
            tmp[idx++] = x;
        }
        Arrays.sort(tmp);
        reflect = new HashMap<>(tmp.length);
        for (int i = 0; i < tmp.length; i++) {
            reflect.put(tmp[i], i + 1);
        }
        tree = new int[tmp.length + 1];
    }

    private void add(int x) {
        for (; x < tree.length; x += lowBit(x)) {
            tree[x]++;
        }
    }

    private int query(int x) {
        int res = 0;
        for (; x > 0; x -= lowBit(x)) {
            res += tree[x];
        }
        return res;
    }

    private int lowBit(int x) {
        return x & -x;
    }
}

刷题总结

逆序对这类题目基本上已经讲解完毕了，小伙伴们可以进行扩展，如果想计算右侧大于当前元素的个数，左侧小于当前元素的个数，左侧大于当前元素的个数应该怎么求解呢？如果计算小于等于当前元素的个数呢？

这里进行提示，小伙伴们可以课后去实现。

右侧大于当前元素的个数，可以将元素取反即可。
左侧小于当前元素的个数，就是将数组逆序，最后将结果数组逆序。
左侧大于当前元素的个数，就是将数组逆序并取反、最后将结果数组逆序。
带等于号的数量，就是在树状数组查询的时候，不减1即可。