Leetcode刷题java之384. 打乱数组（一天一道编程题之二十六天）

素颜马尾好姑娘i 2023-07-15 13:12 13阅读 0赞

执行结果：

通过

显示详情

执行用时 :103 ms, 在所有 Java 提交中击败了72.20% 的用户

内存消耗 :51.3 MB, 在所有 Java 提交中击败了99.22%的用户

题目：

打乱一个没有重复元素的数组。

示例:

// 以数字集合 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();

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shuffle-an-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

每次选择i到最后随机的一个位置和i位置上的换位，就实现了乱序。

需要注意的地方是Random的nextInt方法，还有就是范围。

另外一个就是ori再reseize的时候还要克隆一次

代码：

class Solution {
        private int[] array;
        private int[] ori;
        Random r=new Random();
        private void swap(int i,int j)
        {
            int temp=array[i];
            array[i]=array[j];
            array[j]=temp;
        }
        private int getRandom(int min,int max)
        {
            return r.nextInt(max-min)+min;
        }
        public Solution(int[] nums) {
            array=nums;
            ori=array.clone();
        }
        
        /** Resets the array to its original configuration and return it. */
        public int[] reset() {
            array=ori;
            //因为original的地址被赋给了array，但在shuffle方法里面被修改了。如果不克隆的话，reset返回的数组和shuffle返回的数组是一样的乱序。
            ori=ori.clone();
            return ori;
        }
        
        /** Returns a random shuffling of the array. */
        public int[] shuffle() {
            for(int i=0;i<array.length;i++)
            {
                swap(i,getRandom(i,array.length));
            }
            return array;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(nums);
     * int[] param_1 = obj.reset();
     * int[] param_2 = obj.shuffle();
     */