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

题目

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

解答

https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76584/Mergesort-solution

光头大佬的解法不能通过，但评论中有解法可以通过。。

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        res = [0]*len(nums)
        tupn = [(n, i) for i, n in enumerate(nums)]

        def divide(tupn):
            if len(tupn) == 1:
                return tupn
            mid = len(tupn)//2
            left = divide(tupn[:mid])
            right = divide(tupn[mid:])
            return conquer(left, right)

        def conquer(left, right):
            sor = []
            i = j = 0
            while i < len(left) and j < len(right):
                if left[i][0] > right[j][0]:
                    sor.append(left[i])
                    res[left[i][1]] += len(right)-j
                    i += 1
                else:
                    sor.append(right[j])
                    j += 1
            sor.extend(left[i:] or right[j:])
            return sor

        divide(tupn)
        return res

Runtime: 176 ms, faster than 40.67% of Python3 online submissions for Count of Smaller Numbers After Self.

Memory Usage: 17.1 MB, less than 37.50% of Python3 online submissions for Count of Smaller Numbers After Self.