归并排序（一）：计算右侧小于当前元素的个数

归并排序（一）：计算右侧小于当前元素的个数

原题：

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

示例 1：

输入：nums = [5,2,6,1]
输出：
[2,1,1,0]
解释：

5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

解：

class Solution:
    def countSmaller(self, nums):
        n = len(nums)
        if n == 0:
            return []
        numsarr = [[nums[i], i] for i in range(n)]
        res = [0 for _ in range(n)]
        def merge(left, right):
            print("Entering merge function with left =", left, "and right =", right)
            if left == right:
                pass
            else:
                mid = left + (right - left) // 2
                print("Splitting into left =", left, ", mid =", mid, "and right =", right)
                merge(left, mid)
                print("分为merge",left,"和",right)
                merge(mid + 1, right)
                temp = []
                i = left
                j = mid + 1
                while i <= mid and j <= right:
                    if numsarr[i][0] <= numsarr[j][0]:
                        temp.append(numsarr[j])
                        j += 1
                        print("此时i,j,temp情况", i, j,temp)
                    else:
                        temp.append(numsarr[i])
                        res[numsarr[i][1]] += right - j + 1
                        i += 1
                        print("此时i,j,temp情况", i, j,temp)
                print("调换顺序后当前的temp列表",temp)
                while i <= mid:
                    temp.append(numsarr[i])
                    i += 1
                print("添加左边单个元素的temp列表", temp)
                while j <= right:
                    temp.append(numsarr[j])
                    j += 1
                print("添加右边单个元素的temp列表", temp)
                numsarr[left : right + 1] = temp[:]
                print("新的Numsarr",numsarr)
        merge(0, n - 1)
        return res

if __name__ == '__main__':
    a = Solution()
    nums=[5,2,1,6]
    print(a.countSmaller(nums))
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
36
37
38
39
40
41
42
43
44
45
46
47
48

代码解释

numsarr[left : right + 1] = temp[:] 这行代码是用来将临时列表 temp 中的元素赋值回原始列表 numsarr 的一个切片赋值操作。

让我们逐步解释这行代码：

numsarr: 这是一个二维列表，其每个元素是一个包含两个值的列表 [nums[i], i]。其中，nums[i] 是原始列表 nums 中的元素，而 i 是该元素在原始列表 nums 中的索引位置。

temp: 这是一个临时列表，在合并过程中用于存储两个有序子列表的合并结果。

numsarr[left : right + 1]: 这是一个切片操作，它表示从 numsarr 列表中取出索引从 left 到 right 的所有元素，包含 left 和 right 所在的位置。

temp[:]: 这是一个切片操作，表示将 temp 列表的所有元素复制一份。

numsarr[left : right + 1] = temp[:]: 这行代码将 temp 列表的所有元素赋值回 numsarr 中从 left 到 right 的位置上，用以更新排序后的列表 numsarr。

这个赋值操作实际上是将合并后的有序子列表 temp 的值覆盖了原始列表 numsarr 中相应位置的值，从而完成了归并排序中合并两个有序子列表的操作。

通过这种方式，合并过程中的有序子列表逐渐被正确地放置回原始列表 numsarr 的相应位置，最终在归并排序完成后，numsarr 将变成一个有序列表。同时，由于在合并过程中，代码会根据子列表的位置更新 res 列表中对应元素的值，从而计算每个元素的右侧小于当前元素的个数。

算法思路

在这个特定的问题中，使用了归并排序的思想，通过合并有序的子列表并在合并的过程中计算右侧小于当前元素的个数。
上述代码中使用了一个定义的temp，来更新每次排序后的子序列。
归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的排序算法。它的基本思想是将待排序的列表拆分成较小的子列表，然后逐步将这些子列表合并并排序，最终得到一个有序的列表。

归并排序的主要步骤如下：

1. 分解：将待排序的列表不断拆分成较小的子列表，直到每个子列表只包含一个元素，即认为这些单个元素的列表是有序的。

2. 合并：将两个有序的子列表合并成一个有序的列表。合并过程中，比较两个子列表的首个元素，将较小的元素放入合并后的列表，并继续比较下一个元素，重复这个过程直到两个子列表都合并完毕。

3. 递归：重复上述分解和合并的过程，对每个子列表递归地进行排序。

归并排序的关键在于合并两个有序的子列表，这个合并过程是稳定且高效的。通过不断地递归分解和合并，最终将整个列表排序完成。

归并排序的时间复杂度是 O(n log n)，其中 n 是列表的长度。它的优势在于其稳定的性能和适用于大规模数据的排序。然而，归并排序需要额外的内存空间来存储中间结果，因此在某些情况下可能不适用于内存有限的场景。

总的来说，归并排序是一种效率高且稳定的排序算法，适用于各种数据规模的排序任务。