384 打乱数组

题目信息

题目地址:https://leetcode-cn.com/problems/shuffle-an-array/

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

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

示例:

输入
["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 -106 <= nums[i] <= 106 nums 中的所有元素都是 唯一的 最多可以调用 5 * 104 次 reset 和 shuffle

解法一:暴力

题目意思是让我们实现一个类,它测试就会创建对象并且调用打乱方法与重置方法。既然有重置的话打乱的修改不是在原数组上进行。第一是新数组第二是随机位置。

那我们就可以使用ArrayList与Random来实现

代码如下

class Solution {
    // 原数组、打乱返回数组、随机数
    private int[] nums;
    private int[] result;
    private Random rand = new Random();
    // 构造器初始化原数组与打乱数组的空间
    public Solution(int[] nums) {
        this.nums = nums;
        result = new int[nums.length];
    }
    // 重置方法:即返回原数组
    public int[] reset() {
        return nums;
    }
    // 打乱方法:arrayList随机取[0,size)
    public int[] shuffle() {
        //获取原数组的arrayList
        List<Integer> arrayList = getArrayList();
        for (int i = 0; i < nums.length; i++) {
            int index = rand.nextInt(arrayList.size());
            result[i] = arrayList.get(index);
            arrayList.remove(index);
        }
        return result;
    }
    // 获取List方法
    private List<Integer> getArrayList() {
        List<Integer> arrayList = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            arrayList.add(nums[i]);
        }
        return arrayList;
    }
}

时间复杂度:最差有(51024)(n/2)*n,总体来说O(n^2)的时间复杂度 空间复杂度:由于要用额外数组无法避免的O(n)

解法二:优化

上面的解法效率确实是不够的,其实之前做了那么一系列数组的算法题,虽然都是初级合集的但明显我们能明白一个关于数组原地变换的一个点,就是通过交换减少规模 但这一题并不能让我们通过交换来减少一半的规模,因为随机取再与后面的交换虽然能达到一半的复杂度并全员随机打乱,但并不是完全随机。所以我们还是要遍历完整每个进行random,这样做还是有个好处就是不需要arrayList了这样可以将n^2的复杂度降为n

代码如下:

class Solution {
    private int[] nums;
    private int[] result;
    Random random = new Random();

    public Solution(int[] nums) {
        this.nums = nums;
        result = nums.clone();
    }
    
    public int[] reset() {
        result = nums;
        nums = nums.clone();
        return result;
    }
    
    public int[] shuffle() {
        for (int i = 0; i < result.length; i++) {
            int index = random.nextInt(result.length - i) + i;
            int temp = result[index];
            result[index] = result[i];
            result[i] = temp;
        }
        return result;
    }
}

空间复杂度:O(n) 时间复杂度:O(n)

总结

这一题主要需要考虑打乱是一个什么状态,操作逻辑有没有影响到“随机”,关于解法一与二采用了两种方式记录原数组与打乱的过程数组,由于解法一的打乱赋值过程分了两个容器list和result所以才可以简略的这样写一个空数组,每次都是完全的按照阶乘的一个选取情况。解法二为了减少生成list所带来n倍的复杂度,采用交换,这样就需要在打乱数组本身原地进行,如果是在原数组取一对赋值到打乱数组那么就会出现重复。还有一个点是重置方法的,我在解法一直接是返回原数组只能说在当前逻辑上是满足,但最好还是像解法二一样真正的对打乱数组进行还原而不是把原数组返回出去。并且这里有个需要注意的点,我们在数组赋值实际上指向同一个对象,整个时候我们重置了result数组但result数组改变会影响原数组nums也就是我们要把nums指向另一个,也就是nums = nums.clone();

- END -

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 384. 打乱数组(rand)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shuffle-an-array 著作权归领扣网络所...

    Michael阿明
  • 打乱数组

    按照我们正常的抽奖的最简单做法,一般是把工号写到一个球上面,摇 n 次,然后每次摇出1个号,该号码即为中奖号码,同时将该球拿出去,重复 n 次。

    木子星兮
  • 随机打乱一个数组的例子

    随机打乱一个数组(比如斗地主发牌会用上!) Run.java importjava.util.Random; publicclass Run { R...

    Java学习
  • 打乱数组顺序的三种方法

    刚刚看了文章《常用的sort打乱数组方法真的有用?》,才发现原来此种方法的缺陷,误导了大家,对不起!下边是《常用的sort打乱数组方法真的有用?》文章中提供的一...

    Rattenking
  • 将数组内的元素随机打乱

    OECOM
  • [Python3 开发技巧]·如何打乱字典中多个对应数组

    当我们把数个对应数组保存到字典中,在我们读取的时候这些数据会按照我们保存的顺序读取出来。如果我们需要打乱顺序,但不改变对应数组的关系时,例如原先位置0对应的各个...

    小宋是呢
  • 常用的sort打乱数组方法真的有用?

    mcq
  • js关键词变色,数组打乱,数组去重的实现和封装

    今天,把自己之前封装过的一部分小功能操作分享出现,都是一些可以说是比较常用,实现起来比较简单,代码又比较少的一些功能或操作,比如关键词变色,数组打乱,数组去重等...

    守候i
  • 数组完全乱序

    但是sort并不是真正意义上的乱序,一些元素间并没有机会相互比较(也就没有了随机交换的可能性),所有数组元素在大概率上还停留在自己初始位置。

    OBKoro1
  • 前端刷题BFE.dev #8. shuffle()随机打乱一个数组

    目标就是随机打乱数组,很简单貌似。因为随机打乱意思就是随机的从所有的排列中选取一个,所以可以按照位置顺序,随机的从剩余的位置中选择元素并交换即可。

    JSer
  • 利用GPU模拟心脏研究

    心脏疾病位于全球死亡之首。心脏节律紊乱或者心律失常,是值得认真关注的问题。 为了能阻止这种疾病的破坏性,位于澳大利亚达令赫斯特的Victor Chang 心...

    GPUS Lady
  • vue v-for 数组乱序

    <div v-for="item in items" :key="item.id"></div>

    小贝壳
  • python 之双色球预测

    py3study
  • TCP

    学习 TCP 协议,首先第一个要了解当然是 TCP 连接是如何建立的,下面给大家介绍一下三次握手和四次挥手的过程以及为什么要这样设计。

    IT技术小咖
  • 使用Keras中的ImageDataGenerator进行批次读图方式

    ImageDataGenerator位于keras.preprocessing.image模块当中,可用于做数据增强,或者仅仅用于一个批次一个批次的读进图片数据...

    砸漏
  • 资源 | 对比ResNet: 超深层网络DiracNet的PyTorch实现

    机器之心
  • Element多选框组el-checkbox-group,重新勾选时不希望数组顺序被打乱

    之前一直没注意到一个问题,就是el-checkbox-group选择的顺序是按照点击的多选框的顺序,而不是按照多选框的排列顺序。但是我们不希望它的顺序被打乱,有...

    用户2323866
  • keras实现多种分类网络的方式

    由于AlexNet采用的是LRN标准化,Keras没有内置函数实现,这里用batchNormalization代替

    砸漏
  • lib-flexible适配大屏方案(附移动端适配)

      相信大多数移动端前端开发者都是用过 lib-flexible来作为移动端适配的解决方案。lib-flexible是淘宝项目组开发出来的一个小插件,属于开源项...

    流眸

扫码关注云+社区

领取腾讯云代金券