315. Count of Smaller Numbers After Self

[Tcdian]

315. Count of Smaller Numbers After Self

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

Example

Input: [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.

[Tcdian]

Solution 1 ( Divide and Conquer )

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
    const counts = new Array(nums.length).fill(0);
    const pairs = nums.map((num, index) => [num, index]);
    mergeSort(0, nums.length - 1);
    return counts;

    function mergeSort(left, right) {
        if (left >= right) {
            return pairs.slice(left, right + 1);
        }
        const separator = (left + right) >> 1;
        const leftSorted = mergeSort(left, separator);
        const rightSorted = mergeSort(separator + 1, right);
        let leftIndex = 0;
        let rightIndex = 0;
        const sorted = [];
        while (leftIndex < leftSorted.length) {
            while(rightIndex < rightSorted.length && leftSorted[leftIndex][0] > rightSorted[rightIndex][0]) {
                sorted.push(rightSorted[rightIndex++]);
            }
            counts[leftSorted[leftIndex][1]] += rightIndex;
            sorted.push(leftSorted[leftIndex++]);
        }
        sorted.push(...rightSorted.slice(rightIndex));
        return sorted;
    }
};

• TypeScript Solution

function countSmaller(nums: number[]): number[] {
    const counts: number[] = new Array(nums.length).fill(0);
    const pairs: [number, number][] = nums.map((num, index) => [num, index]);
    mergeSort(0, nums.length - 1);
    return counts;

    function mergeSort(left: number, right: number): [number, number][] {
        if (left >= right) {
            return pairs.slice(left, right + 1);
        }
        const separator = (left + right) >> 1;
        const leftSorted = mergeSort(left, separator);
        const rightSorted = mergeSort(separator + 1, right);
        let leftIndex = 0;
        let rightIndex = 0;
        const sorted: [number, number][] = [];
        while (leftIndex < leftSorted.length) {
            while(rightIndex < rightSorted.length && leftSorted[leftIndex][0] > rightSorted[rightIndex][0]) {
                sorted.push(rightSorted[rightIndex++]);
            }
            counts[leftSorted[leftIndex][1]] += rightIndex;
            sorted.push(leftSorted[leftIndex++]);
        }
        sorted.push(...rightSorted.slice(rightIndex));
        return sorted;
    }
};

[Tcdian]

Solution 2 ( Binary Search Tree )

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
    const counts = new Array(nums.length).fill(0);
    let root = null;
    for (let i = nums.length - 1; i >= 0; i--) {
        root = insert(root, nums[i], i);
    }
    return counts;

    function insert(root, val, index) {
        if (root === null) {
            return new BSTNode(val);
        }
        if (root.val >= val) {
            root.leftChildCount += 1;
            root.left = insert(root.left, val, index);
        } else {
            counts[index] += root.leftChildCount + 1;
            root.right = insert(root.right, val, index);
        }
        return root;
    }
};

function BSTNode(val) {
    this.val = val;
    this.leftChildCount = 0;
    this.left = this.right = null;
}

• TypeScript Solution

class BSTNode {
    public leftChildCount: number;
    public left: BSTNode | null;
    public right: BSTNode | null;
    constructor(public val: number) {
        this.leftChildCount = 0;
        this.left = this.right = null;
    }
}

function countSmaller(nums: number[]): number[] {
    const counts: number[] = new Array(nums.length).fill(0);
    let root = null;
    for (let i = nums.length - 1; i >= 0; i--) {
        root = insert(root, nums[i], i);
    }
    return counts;

    function insert(root: BSTNode | null, val: number, index: number): BSTNode {
        if (root === null) {
            return new BSTNode(val);
        }
        if (root.val >= val) {
            root.leftChildCount += 1;
            root.left = insert(root.left, val, index);
        } else {
            counts[index] += root.leftChildCount + 1;
            root.right = insert(root.right, val, index);
        }
        return root;
    }
};