力扣刷题笔记 → 384 打乱数组

发表于

这是我参与11月更文挑战的第22天，活动详情查看：2021最后一次更文挑战

题目

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

  • Solution(int[] nums) 使用整数数组 nums 初始化对象
  • int[] reset() 重设数组到它的初始状态并返回
  • int[] shuffle() 返回数组随机打乱后的结果

示例

1
2
3
4
5
6
7
8
9
10
11
css复制代码输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示

  • 1 <= nums.length <= 200
  • -10^6 <= nums[i] <= 10^6
  • nums 中的所有元素都是 唯一的
  • 最多可以调用 5 * 10^4 次 reset 和 shuffle

解题思路

Random随机数

题目中要求我们需要实现两个方法，一个是返回打乱顺序后的数组，一个是返回原数组。对于返回原数组的，我们可以采用空间换时间的方式，定义多一个数组orig用来保存原数组，当调用reset()方法当时候直接将结果返回即可。

至于打乱顺序的方法，我们可以直接使用现成的API Random 来实现。通过随机交换数组中元素位置，实现乱序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
java复制代码class Solution {
    private static final Random random = new Random();
    private int[] orig;
    private int[] nums;

    public Solution(int[] nums) {
        this.orig = nums;
        this.nums = new int[nums.length];
        int index = 0;
        for(int num : nums){
            this.nums[index++] = num;
        }
    }
    
    public int[] reset() {
        // 直接返回原数组
        return orig;
    }
    
    public int[] shuffle() {
        int n = nums.length;
        for(int i = 0; i < n; ++i){
            // 随机取得一位元素进行交换
            int j = random.nextInt(n);
            nums[i] = nums[i] + nums[j] - (nums[j] = nums[i]);
        }
        return nums;
    }
}

复杂度分析

  • 时间复杂度：O(N)O(N)O(N)
  • 空间复杂度：O(N)O(N)O(N)

最后

文章有写的不好的地方，请大佬们不吝赐教，错误是最能让人成长的，愿我与大佬间的距离逐渐缩短！

如果觉得文章对你有帮助，请 点赞、收藏、关注、评论 一键四连支持，你的支持就是我创作最大的动力！！！

题目出处: leetcode-cn.com/problems/sh…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%