LeetCode 384. 打乱数组

Categories:

题目描述
思路分析
1. 解法一：Fisher-Yates 洗牌（推荐）
相似题目

题目描述

✅ 384. 打乱数组

思路分析

解法一：Fisher-Yates 洗牌（推荐）

核心思路：

每次从未处理区间中随机选择一个元素，与当前位置交换。

从后往前遍历，保证每个排列等概率出现。

reset 直接返回初始数组的拷贝。

复杂度分析：

时间复杂度：shuffle 为 O(n)，reset 为 O(n)。

空间复杂度：O(n)，保存原数组副本。

class Solution {
    private final int[] original;
    private final Random random = new Random();

    public Solution(int[] nums) {
        original = nums.clone();
    }

    public int[] reset() {
        return original.clone();
    }

    public int[] shuffle() {
        int[] arr = original.clone();

        // Fisher-Yates 洗牌
        for (int i = arr.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        return arr;
    }
}

import "math/rand"

type Solution struct {
    original []int
}

func Constructor(nums []int) Solution {
    copied := append([]int(nil), nums...)
    return Solution{original: copied}
}

func (s *Solution) Reset() []int {
    return append([]int(nil), s.original...)
}

func (s *Solution) Shuffle() []int {
    arr := append([]int(nil), s.original...)

    // Fisher-Yates 洗牌
    for i := len(arr) - 1; i > 0; i-- {
        j := rand.Intn(i + 1)
        arr[i], arr[j] = arr[j], arr[i]
    }

    return arr
}

相似题目

题目	难度	考察点
470. 用 Rand7() 实现 Rand10()	中等	概率
398. 随机数索引	中等	水塘抽样
528. 按权重随机选择	中等	前缀和 + 随机
519. 随机翻转矩阵	中等	随机映射
382. 链表随机节点	中等	水塘抽样

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/77298889