题目:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/24/design/58/
题目描述:
打乱一个没有重复元素的数组。
示例:
// 以数字集合 1, 2 和 3 初始化数组。 int[] nums = {1,2,3}; Solution solution = new Solution(nums);// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。 solution.shuffle();// 重设数组到它的初始状态[1,2,3]。 solution.reset();// 随机返回数组[1,2,3]打乱后的结果。 solution.shuffle();
思路:需要两个数组。一个是记录没变化的数组,一个用于操作。这里没用for循环赋值获得可操作数组。用的是Arrays.copyOf方法。如果直接用 = 号 ,不是复制数组!只是共同引用一个数组的地址!操作部分。用Random类 的ran.nextInt()方法获得伪随机数。然后用一个数记录随机数。随机数的位置和i互换。其中temp 用于记录交换值。
对了,刚开始在构造方法 重新 int[] orgin = nums;是错的!这样全局变量orgin 并没有获得nums地址。
代码:
class Solution {private int[] orgin;private int[] cur;public Solution(int[] nums) {orgin = nums;}/** Resets the array to its original configuration and return it. */public int[] reset() {return orgin;}/** Returns a random shuffling of the array. */public int[] shuffle() {cur = Arrays.copyOf(orgin,orgin.length);Random ran = new Random();for(int i=orgin.length-1;i>=0;i--){int x = ran.nextInt(i+1);int temp = cur[x] ;cur[x]=cur[i];cur[i]= temp;}return cur;}
}