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

描述:

给定一个整数数组 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 个更小的元素.

解析:

这道题可以暴力破解，从左向右逐个遍历小于当前元素的值，时间复杂度是O(n)。 我们这里想说的是另外一个解法，利用归并排序的思路来求解。 首先将nums转化为temp数组，每项的第一个值为num，第二个值为index保留原数组位置信息。对temp数组使用归并排序，在合并过程中当right侧数组值小于left侧时counts[left[l][1]]加一，当left侧值大于right侧值时counts[left[l][1]]加上右侧已经插入过得值，也就是索引r。

时间复杂度: O(nlogn) / 空间复杂度: O(n)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
    if(!nums.length) return []
    const counts = new Array(nums.length).fill(0)
    const temp = nums.reduce((map, num, index)=> {
        map.push([num, index])
        return map
    }, [])
    
    const merge = (left, right) => {
        const arr = []
        let l = 0,
            r = 0
        while(l < left.length && r < right.length) {
            if(left[l][0] > right[r][0]) {
                arr.push(right[r++])
                counts[left[l][1]] += 1
            }else {
                arr.push(left[l++]) 
                if(left[l]) counts[left[l][1]] += r
            }
        }
        for(let index = l + 1; index<left.length; index++) {
            counts[left[index][1]] += right.length
        }
        
        return [...arr, ...left.slice(l), ...right.slice(r)]
    }
    const mergeSort = (arr)=> {
        if(arr.length <= 1) return arr
        const mid = parseInt(arr.length / 2)
        const left = mergeSort(arr.slice(0, mid))
        const right = mergeSort(arr.slice(mid))
        return merge(left, right)
    }
     
    mergeSort(temp)
    return counts
};