随机化算法

本文最后更新于:2024年2月12日 晚上

模拟退火

题目:

1515. 服务中心的最佳位置

数组随机化

题目:

5856. 完成任务的最少工作时间段

Fisher-Yates 洗牌算法

线性时间复杂度打乱数组,先打乱数组,在排序,可以避免快排最坏时间复杂度。

static final Random random = new Random();
static void shuffleSort(int[] a) {
    int n = a.length;//shuffle, then sort 
    for (int i = 0; i < n; i++) {
        int oi = random.nextInt(n), temp = a[oi];
        a[oi] = a[i]; 
        a[i] = temp;
    }
    Arrays.sort(a);
}