算法热题:打乱数组

2021/09/01 13:45
阅读数 212

每日简短一刷,保持手感系列

题目:

给你一个整数数组 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

今天这题目比较简单和直白。

随机就想到Random这个伪随机类来实现就行了。

然后需要定义两个数组,一个来保存初始顺序的数组,它是不变的。

另一个数组则存储每次打乱顺序的值。

答案:

解法一


class Solution {

    private int[] oriNums;
    private int[] shuffles;
    
    private Random rand;

    public Solution(int[] nums) {
      oriNums = nums.clone();
      shuffles = nums;
      rand = new Random();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
      return oriNums;
    } 
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
      List<Integer> list = copyArrayAsList();
      for (int i = 0 ; i < shuffles.length; i++) {
        int index = rand.nextInt(list.size());
        shuffles[i] = list.get(index);
        list.remove(index);
      }
      return shuffles;
    }

    private List<Integer> copyArrayAsList() {
      List<Integer> list = new ArrayList();
      for (int i = 0; i < oriNums.length; i++) {
          list.add(oriNums[i]);
      }
      return list;
    }
}

注意点:

shuffle时间复杂度是n平方,因为 remove 需要遍历 list 列表的。

解法二

那就优化 remove 地方,解法一是利用一个list来移除已经被挑选的值,防止重复选择,这里可以做一波优化。

将它变成数组元素的交换,利用下标的递进来防止重复选择。

class Solution {

    private int[] oriNums;
    private int[] shuffles;

    private Random rand;

    public Solution(int[] nums) {
      oriNums = nums.clone();
      shuffles = nums;
      rand = new Random();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
      return oriNums;
    } 
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
      shuffles = oriNums.clone(); // 保证起始数据都是原有的顺序
      for (int i = 0 ; i < shuffles.length; i++) {
        int index = rand.nextInt(shuffles.length - i) + i;
        swap(i, index);
      }
      return shuffles;
    }

    private void swap(int a, int b) {
        int temp = shuffles[index];
        shuffles[index] = shuffles[i];
        shuffles[i] = temp;
    }
}

这样时间复杂度就变成 O(n)了。


一道中等题,LC地址如下:
https://leetcode-cn.com/problems/shuffle-an-array/

本文分享自微信公众号 - yes的练级攻略(yes_java)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部