2020-07-11 leetcode 计算右侧小于当前元素的个

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

解题思路：

首先尝试暴力法，一般来说最后肯定会超时的，但是试试呗

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        count = [0] * n
        index = 0
        for value in nums:
            for i in range(index + 1,n):
                if nums[i] < value:
                    count[index] += 1
            index += 1
        return count

果然超时，那么我们就想办法优化这个O(n²)的算法，不考虑别的思路的情况下，我们来看这个O(n²)具体干了什么。最外层循环是遍历nums数组，显然这个应该是不好优化的。内层循环是直接统计右边的数组元素计数，这里就可以稍微改动一下。事实上如果我们有一个升序的有序数组，那么我们直接返回下标应该就是我们想要的count值。

[1,2,3,4,5,6,7]
[0,1,2,3,4,5,6]

所以我们的目标就改为给原数组排序，排序时由于有重复的数字情况出现，我们希望新插入的元素可以每次插到相同元素序列的左侧，这样所有的相同元素都会有同一个count。使用bisect模块提供的二分实现bisect_left。

def bisect_left(a, x, lo=0, hi=None):
    '''
    a 原列表
    x 插入的元素
    lo 起始位置 默认值为0
    hi 结束位置 默认值为len(a)
    目的: 查找该数值将会插入的位置并返回，而不会插入。如果x存在在a中则返回x左边的位置。
    '''
    # 如果起始位置小于0 则报错
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # 如果没有 结束位置 则 默认为 列表的长度
    if hi is None:
        hi = len(a)
    # 二分法
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    # 仅返回位置
    return lo

题目的要求与仅仅排序还有一定区别，因为每次仅仅与右侧元素相比，所以向a列表中放元素时，从后往前放，才能得到正确答案

完整代码：

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        '''
        sort_nums中是一直升序有序的
        该算法时间复杂度为O(nlogn)
        '''
        n = len(nums)
        count = [0] * n
        sort_nums = []
        for i in range(n-1,-1,-1):
            index = bisect.bisect_left(sort_nums,nums[i])
            sort_nums.insert(index,nums[i])
            count[i] = index
        return count

bisect模块的其他函数：

1、insort_left(a, x, lo=0, hi=None)

def insort_left(a, x, lo=0, hi=None):
    '''
    a 原列表
    x 插入的元素
    lo 起始位置 默认值为0
    hi 结束位置 默认值为len(a)
    目的：在列表a中插入元素x，并在排序后保持排序。如果x已经在a中，把它插入右x的左边。
    '''
    # 如果起始位置小于0 则报错
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # 如果没有 结束位置 则 默认为 列表的长度
    if hi is None:
        hi = len(a)
    # 二分查找
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    # 插入
    a.insert(lo, x)

2、insort_right(a, x, lo=0, hi=None)

def insort_right(a, x, lo=0, hi=None):
    '''
    a 原列表
    x 插入的元素
    lo 起始位置 默认值为0
    hi 结束位置 默认值为len(a)
    目的：在列表a中插入元素x，并在排序后保持排序。如果x已经在a中，把它插入右x的右边。
    '''
    # 如果起始位置小于0 则报错
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # 如果没有 结束位置 则 默认为 列表的长度
    if hi is None:
        hi = len(a)
    # 二分法查找 
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    # 插入
    a.insert(lo, x)

3、bisect_right(a, x, lo=0, hi=None)

def bisect_right(a, x, lo=0, hi=None):
    '''
    a 原列表
    x 插入的元素
    lo 起始位置 默认值为0
    hi 结束位置 默认值为len(a)
    目的：其目的在于查找该数值将会插入的位置并返回，而不会插入。如果x存在在a中则返回x右边的位置
    '''
    # 如果起始位置小于0 则报错
    if lo < 0:
        raise ValueError('lo must be non-negative')
    # 如果没有 结束位置 则 默认为 列表的长度
    if hi is None:
        hi = len(a)
    # 二分法
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    # 仅返回位置
    return lo

还要学习的其他解法：

1. 归并排序
2. BST
3. 树状数组
4. 线段树