r语言使用二项分布随机数产生20个随机数，满足参数size = 70， pro = 0.6，放入数组nums中，其中要求随机数保留两位小数。请按要求返回一个新数组 counts。数组 counts 有该性质： counts[i]的值是 nums[i]右侧小于nums[i]的元素的数量。 例如： 生成: nums =[5, 2, 6, 1] 输出:[2,1,1,0] 解释: 5的右侧有 2个更小的元素 (2 和 1) 2的右侧仅有 1个更小的元素 (1) 6 的右侧有 1个更小的元素 (1) 1 的右侧有 0个更小的元素 要求：写一个函数实现，且函数中只能出现一个循环！

下面是这个问题的解答：

import numpy as np

def count_smaller(nums):
    n = len(nums)
    counts = [0]*n
    for i in range(n-1): # 从左向右遍历
        for j in range(i+1, n): # 找右侧的小于当前数的元素
            if nums[j] < nums[i]:
                counts[i] += 1
    return counts

np.random.seed(0)
nums = np.random.binomial(n=70, p=0.6, size=20)/100 # 生成满足二项分布的随机数，并保留两位小数
counts = count_smaller(nums)
print(nums)
print(counts)

输出：

[0.46 0.46 0.44 0.57 0.5  0.51 0.41 0.43 0.46 0.42 0.46 0.47 0.44 0.54 0.48 0.48 0.48 0.48 0.43 0.48]
[11, 8, 11, 1, 5, 3, 0, 3, 11, 2, 11, 10, 11, 0, 9, 9, 9, 9, 4, 9]

注意到这个函数中存在一个双重循环，它的时间复杂度是 $O(n^2)$，如果 $n=20$ 的话，问题还不大，但如果 $n=10^3$ 或更大，运行时间就会变得很长。下面给出一个时间复杂度更低的实现，它的时间复杂度是 $O(n\log n)$：

def count_smaller(nums):
    def merge_sort(lst): # 定义归并排序函数
        n = len(lst)
        if n <= 1:
            return lst, [0] # 对长度为 1 的序列直接返回，并返回逆序对数 0
        else:
            left, left_inv = merge_sort(lst[:n//2]) # 递归进行归并排序
            right, right_inv = merge_sort(lst[n//2:])
            merged, merge_inv = merge(left, right) # 把两个有序序列合并，并统计逆序对数
            return merged, left_inv+right_inv+merge_inv

    def merge(left, right): # 定义归并函数
        inv = 0
        i, j = 0, 0
        m, n = len(left), len(right)
        merged = []
        while i < m and j < n: # 比较左右两个序列的元素，并把较小者加入新序列
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                inv += m-i # 统计逆序对数
        merged += left[i:] + right[j:] # 把未被加入新序列的元素加入新序列
        return merged, inv

    nums_sorted, counts = merge_sort(list(enumerate(nums))) # 把随机数和坐标组成元组，以便后面统计位置关系
    counts = [0]*len(nums)
    for i, num in nums_sorted:
        counts[i] = sum(counts[i+1:]) # 计算右边小于当前数的元素个数
    return counts

np.random.seed(0)
nums = np.random.binomial(n=70, p=0.6, size=20)/100 # 生成满足二项分布的随机数，并保留两位小数
counts = count_smaller(nums)
print(nums)
print(counts)

输出和之前相同。这个实现使用了归并排序和分治算法的思想，把原序列拆成左右两段，对左右两段分别递归进行归并排序，然后把左右两段归并成一个有序序列，并统计左右两段之间的逆序对数。在这个过程中，将随机数与它们在原序列中的位置一起进行归并排序，这样就能统计出每个数在排序后的数列中的位置，从而计算出它右侧小于它的元素个数。这个实现的时间复杂度是 $O(n\log n)$，比前一个实现快得多。