递归循环中使用random随机数

a. 该方法采用的是递归算法。当随机生成的数字小于等于 a 时，该方法会递归调用自身，直到生成的数字大于 a 为止。 b. 代码中存在以下问题： 1. 方法名应该使用小写字母开头，符合 Java 命名规范。 2. 方法应该添加访问修饰符，比如 `public`。 3. `Random.nextInt()` 方法的参数应该是整数，而代码中使用了 `b`。 4. 递归调用时应该使用 `return` 关键字返回结果，而代码中没有使用 `return`。 5. 当递归调用时，没有限制递归的深度，可能会导致栈溢出。 6. 如果参数 `a` 的值大于等于 `b` 的值，该方法会进入死循环，应该在方法开始时添加判断避免这种情况。 下面是修改后的代码： ``` public int randG(int a, int b) { if (a >= b) { throw new IllegalArgumentException("a must be smaller than b"); } Random r = new Random(); int t = r.nextInt(b - a) + a; if (t > a) { return t; } else { return randG(a, b); } } ``` 修改后的代码中，使用 `IllegalArgumentException` 抛出异常，避免了参数 `a` 大于等于 `b` 时进入死循环的情况，使用 `return` 关键字返回结果，避免了递归调用时返回结果错误的问题，使用 `nextInt(b - a) + a` 生成大于等于 `a`、小于 `b` 的随机数，避免了原代码中使用了错误的参数的问题。

下面是这个问题的解答： ```python 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)$： ```python 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)$，比前一个实现快得多。