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

🎯 问题描述（来源于LeetCode）

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

  • 1 <= nums.length <= 105

  • -104 <= nums[i] <= 104
    示例：

  • 示例 1：

1
2
3
4
5
6
7
输入：nums = [5,2,6,1]
输出：[2,1,1,0]  
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有1个更小的元素 (1)
1 的右侧有0个更小的元素
  • 示例 2：
1
2
输入：nums = [-1]
输出：[0]

💻 解题思路

思路1：在归并过程中计数

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n        
        arr = [(nums[i], i) for i in range(n)]
        def merge_sort(arr, left, right):
            if left >= right:
                return
            mid = (left + right) // 2
            merge_sort(arr, left, mid)
            merge_sort(arr, mid + 1, right)
            merge(arr, left, mid, right)
        def merge(arr, left, mid, right):
            temp = []
            i, j = left, mid + 1
            while i <= mid and j <= right:
                if arr[i][0] <= arr[j][0]:
                    ans[arr[i][1]] += (j - (mid + 1))
                    temp.append(arr[i])
                    i += 1
                else:
                    temp.append(arr[j])
                    j += 1
            while i <= mid:
                ans[arr[i][1]] += (j - (mid + 1))
                temp.append(arr[i])
                i += 1
            while j <= right:
                temp.append(arr[j])
                j += 1
            for k in range(left, right + 1):
                arr[k] = temp[k - left]
        
        merge_sort(arr, 0, n - 1)
        return ans

思路1：📊 性能分析

提交结果
  • 运行时间：1459ms击败39.86%
  • 内存消耗：47.17MB击败36.36%
复杂度验证
  • 时间复杂度：O(NLogN)O(NLogN)
  • 空间复杂度：O(N)O(N)

思考

归并过程实际上已经在对逆序对小于数计数了，我们只需要在过程将其记录即可