0315. Count of Smaller Numbers After Self - kumaeki/LeetCode GitHub Wiki

0315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

解法1

在 0307. Range Sum Query Mutable 的结构基础之上稍加改造.

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        // 数字范围是-10000到10000, 一共20001个数字
        int[] arr = new int[20001];
        
        int len = nums.length;
        // 307 的数据结构
        // 下标表示数字, 值表示该数字出现的次数
        NumArray na = new NumArray(arr);
        // 因为有负数, 对应的下标需要加10000
        // 比如最小值-10000, 在na中的位置就是 -10000 + 10000 = 0
        na.update(nums[len - 1] + 10000, 1);

        // 最后一位
        Integer[] result = new Integer[len];
        result[len - 1] = 0;

        // 从倒数第二位开始往左计算
        for (int i = len - 2; i >= 0; i--) {
            int num = nums[i];
            // 比num小的数字出现的总次数
            result[i] = na.getCountSmaller(num + 10000);
            // num的出现次数加1
            na.update(num + 10000);
        }

        return Arrays.asList(result);
    }

    class NumArray {

        int[] tree, nums;
        int n;

        public NumArray(int[] nums) {
            this.n = nums.length;
            this.nums = new int[n];
            this.tree = new int[n + 1];
            for (int i = 0; i < n; i++)
                update(i, nums[i]);
        }

        private int getNext(int n) {
            return n & -n;
        }
        
        // 当前位置数字加1
        public void update(int i) {
            update(i, nums[i] + 1);
        }

        public void update(int i, int val) {
            int dif = val - nums[i];
            nums[i] = val;
            i++;
            while (i <= n) {
                tree[i] += dif;
                i += getNext(i);
            }
        }

        public int sumRange(int i, int j) {
            return getSum(j + 1) - getSum(i);
        }

        // 对位置在i之前(不包括)的所有的值求和
        public int getCountSmaller(int i) {
            return getSum(i);
        }

        private int getSum(int i) {
            int res = 0;
            while (i > 0) {
                res += tree[i];
                i -= getNext(i);
            }
            return res;
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️