如何创建降序排列的数组,现有实现是否有更高效的优化方案?
实现优化方案
你的现有实现逻辑正确,整体时间复杂度为O(n log n),可以从以下两个方向优化效率:
1 通用场景基础优化(保留原排序逻辑)
你当前每次调用方法都会新建Random实例,短时间高频调用时既可能生成重复的随机序列,也会产生不必要的初始化开销,建议将Random抽为静态常量复用。
这种方案下你的排序+反转逻辑已经是同思路下的最优实现:Arrays.sort采用的双轴快排性能已经经过JDK深度优化,手动反转数组的O(n)开销极低,远优于转成Integer数组后传入降序比较器排序的方案(后者存在拆箱装箱的额外性能损耗)。
优化后的基础版本代码:
import java.util.Arrays; import java.util.Random; public class ArrayGenerator { private static final Random RANDOM = new Random(); public static int[] createRandomIntArray(int n) { if (n <= 0) { return new int[0]; } int[] result = new int[n]; for (int i = 0; i < n; i++) { result[i] = RANDOM.nextInt(n); } Arrays.sort(result); // 反转数组 for (int i = 0; i < result.length / 2; i++) { int temp = result[i]; result[i] = result[result.length - i - 1]; result[result.length - i - 1] = temp; } return result; } }
2 针对当前随机数范围的高性能优化(时间复杂度降至O(n))
注意到你当前使用random.nextInt(n)生成随机数,所有元素的取值范围固定为[0, n-1],刚好符合计数排序的适用条件,用计数排序可以直接生成降序数组,完全省去排序和反转的步骤,n越大性能提升越明显。
优化后代码:
import java.util.Random; public class ArrayGenerator { private static final Random RANDOM = new Random(); public static int[] createRandomIntArray(int n) { if (n <= 0) { return new int[0]; } // 统计每个数字出现的次数 int[] count = new int[n]; for (int i = 0; i < n; i++) { count[RANDOM.nextInt(n)]++; } // 从大到小填充结果数组 int[] result = new int[n]; int index = 0; for (int num = n - 1; num >= 0; num--) { while (count[num] > 0) { result[index++] = num; count[num]--; } } return result; } }
内容的提问来源于stack exchange,提问作者Ezequiel Soler
相关产品推荐
相关产品推荐

