每日简短一刷,保持手感系列
题目:
给你一个整数数组 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这个伪随机类来实现就行了。

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

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

解法一


classSolution
{


privateint
[] oriNums;

privateint
[] shuffles;


private
 Random rand;


publicSolution(int[] nums)
{

      oriNums = nums.clone();

      shuffles = nums;

      rand = 
new
 Random();

    }


/** Resets the array to its original configuration and return it. */
publicint
[] reset() {

return
 oriNums;

    } 


/** Returns a random shuffling of the array. */
publicint
[] 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来移除已经被挑选的值,防止重复选择,这里可以做一波优化。
将它变成数组元素的交换,利用下标的递进来防止重复选择。
classSolution
{


privateint
[] oriNums;

privateint
[] shuffles;


private
 Random rand;


publicSolution(int[] nums)
{

      oriNums = nums.clone();

      shuffles = nums;

      rand = 
new
 Random();

    }


/** Resets the array to its original configuration and return it. */
publicint
[] reset() {

return
 oriNums;

    } 


/** Returns a random shuffling of the array. */
publicint
[] 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;

    }


privatevoidswap(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/
继续阅读
阅读原文