经典题目

华为机试. 小朋友送祝福问题

暴力解法
我们从nums数组的右边向左边遍历，然后再从当前值向右边遍历找到所有比当前值小的值的个数，时间复杂度为O(n^2)，超时。
如果我们 统计当前遇到的数字出现的次数数组a，a是一个有序的桶，用来存放各个值出现的次数，这样我们只需要在a中找所有比当前值小的值出现的次数求和即可，这样能稍微降下复杂度，但是也是O(n^2)
树状数组
用树状数组存储，根据a计算得到树状数组c，再根据求sum的方法求bless数组。
离散化是优化空间的做法，离散化之后二分找到值的下标

public class Main {
    private int[] sorted;
    private int[] tree;
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> resultList = new ArrayList<Integer>();
        discretization(nums);
        tree = new int[nums.length + 1];
        for (int i = nums.length - 1; i >= 0; --i) {
            int id = getId(nums[i]); //找到当前值对应的数组下标
            resultList.add(query(id - 1)); //要比当前值小
            update(id); //当前值的次数加1
        }
        Collections.reverse(resultList);
        return resultList;
    }
    private int lowBit(int x) {
        return x & (-x);
    }
    private void update(int pos) {
        while (pos < tree.length) {
            tree[pos] += 1;
            pos += lowBit(pos);
        }
    }
    private int query(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret += tree[pos];
            pos -= lowBit(pos);
        }
        return ret;
    }
    private void discretization(int[] nums) {
        sorted = new int[nums.length];
        int index = 0;
        for (int num : nums) {
            sorted[index++] = num;
        }
        Arrays.sort(sorted);
    }
    private int getId(int x) {
        return Arrays.binarySearch(sorted, x) + 1;
    }
}

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

「该题跟上一题的唯一区别就是，该题需要去重」
极好的题解

public class Main {

    private int[] sorted;
    private int[] tree;

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> resultList = new ArrayList<Integer>();
        discretization(nums);
        tree = new int[nums.length + 1];

        for (int i = nums.length - 1; i >= 0; --i) {
            int id = getId(nums[i]); //找到当前值对应的数组下标
            resultList.add(query(id - 1)); //要比当前值小
            update(id); //当前值的次数加1
        }

        Collections.reverse(resultList);
        return resultList;
    }


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

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

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

    private void discretization(int[] nums) {
        //先去重
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        sorted = new int[set.size()];
        int index = 0;
        for (int num : set) {
            sorted[index++] = num;
        }
        Arrays.sort(sorted);
    }

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

剑指 Offer 51. 数组中的逆序对

一模一样的套路

class Solution {
    int[] tree;
    int[] sorted;

    public int reversePairs(int[] nums) {
        int res = 0;
        init(nums);
        discretization(nums);

        for (int i = nums.length - 1; i >= 0; --i) {
            int idx = getId(nums[i]);
            update(idx, 1);
            res +=query(idx - 1);
        }

        return res;
    }

    int lowBit(int i ){
        return i & (-i);
    }

    void update(int i, int delta) {
        while (i < tree.length) {
            tree[i] += delta;
            i += lowBit(i);
        }
    }

    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowBit(i);
        }
        return sum;
    }

    void init(int[] nums) {
        tree = new int[nums.length + 1];
    }

    void discretization(int[] nums){
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        sorted = new int[set.size()];
        int index = 0;
        for (int num : set) {
            sorted[index++] = num;
        }
        Arrays.sort(sorted);
    }

    int getId(int num) {
        return Arrays.binarySearch(sorted, num) + 1;
    }
}