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

难度

• Easy
• Medium
• Hard

思路

跟 剑指 Offer 51. 数组中的逆序对 非常相似，所以也用归并排序来写。

不同之处在于，本题要求知道每一个数对应的右侧逆序数的数目。

用笨一点的方法，在排序的同时，维护一个数组 cnt ，记录每个数字右侧的逆序数的数量。cnt 要跟着 nums 一起排序，所以最后不能直接返回 cnt ，还要根据下标进行还原。故此，还需要一个 indices 数组用于记录当前位置的下标对应于原始顺序的下标。

此外，需要几个 temp 数组用于辅助。

还可以用别的方法，如二分（可能超时了），树状数组（待学习），线段树。

代码

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        cnt = [0 for _ in range(n)]
        temp_nums = list(nums)
        temp_cnt = list(cnt)
        indices = list(range(n))
        temp_indices = list(indices)

        def merge(l: int, r: int) -> None:
            if l >= r: return
            mid = (l + r) >> 1
            merge(l, mid)
            merge(mid + 1, r)
            L, R, cur = l, mid + 1, l
            while L <= mid and R <= r:
                if nums[L] <= nums[R]:
                    temp_nums[cur] = nums[L]
                    temp_cnt[cur] = cnt[L] + R - mid - 1
                    temp_indices[cur] = indices[L]
                    L += 1
                else:
                    temp_nums[cur] = nums[R]
                    temp_cnt[cur] = cnt[R]
                    temp_indices[cur] = indices[R]
                    R += 1
                cur += 1
            while L <= mid:
                temp_nums[cur] = nums[L]
                temp_cnt[cur] = cnt[L] + R - mid - 1
                temp_indices[cur] = indices[L]
                L += 1
                cur += 1
            while R <= r:
                temp_nums[cur] = nums[R]
                temp_cnt[cur] = cnt[R]
                temp_indices[cur] = indices[R]
                R += 1
                cur += 1

            nums[l:r + 1] = temp_nums[l:r + 1]
            cnt[l:r + 1] = temp_cnt[l:r + 1]
            indices[l:r + 1] = temp_indices[l:r + 1]
            return

        merge(0, n - 1)
        ans = [0 for _ in range(n)]
        for i in range(n):
            ans[indices[i]] = cnt[i]
        return ans