题目

image.png

解题思路

  1. /*
  2.             n is the size of the array
  3.             [0...n - 1]
  4.             i [i, n-1]
  6.             i = 0,  [0, n - 1]   1 / n
  7.             i = 1,  [1, n - 1]  ( (n - 1) / n  ) * ( 1 /(n - 1)) = 1 / 
  8.             i = 2    ( (n - 1) / n  ) * ( n - 2 /(n - 1)) * (n - 2 / n - 1)  = 1 / n
  10.                     [i, n - 1]
  11.                     [0, n - 1 - i] + i
  12. */

作者：venturekwok
链接：https://leetcode-cn.com/problems/shuffle-an-array/solution/c-jian-dan-xi-pai-suan-fa-si-lu-qing-xi-pu41a/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题代码

  1. class Solution {
  3.     int[] nums;
  4.     //构造函数，初始化
  5.     public Solution(int[] nums) {
  6.         this.nums = nums;
  7.     }
  9.     //重置
  10.     public int[] reset() {
  11.         return nums;
  12.     }
  14.     //洗牌算法
  15.     public int[] shuffle() {
  17.         if(nums == null) return null;
  19.         int[] res = nums.clone();
  21.         for(int i = 0 ; i < nums.length; i++ ) {
  22.             int random = (int) ( Math.random() * (nums.length - i) ) + i; //[0,1) [i,nums.length -1]
  23.             swap(res,i,random);
  25.         }
  27.         return res;
  28.     }
  30.     public void swap(int[] res, int i, int random) {
  31.             int temp = res[i];
  32.             res[i] = res[random];
  33.             res[random] = temp;
  34.     }
  35. }
  37. /**
  38.  * Your Solution object will be instantiated and called as such:
  39.  * Solution obj = new Solution(nums);
  40.  * int[] param_1 = obj.reset();
  41.  * int[] param_2 = obj.shuffle();
  42.  */
class Solution {

    int [] nums;
    int [] shuffle;
    public Solution(int[] nums) {
        this.nums = nums;
    }

    public int[] reset() {
        return nums;
    }

    public int[] shuffle() {
        int length = nums.length;
        shuffle = nums.clone(); //传值
        for (int i = 0; i < length; i++) {
            int random = (int)(Math.random() * (length - i )) + i;
            swap(i,random);
        }
        return shuffle;
    }

    public void swap(int i ,int j) {
        if(i == j) return ; //相同则不进行交换
        shuffle[i] ^= shuffle[j];
        shuffle[j] ^= shuffle[i];
        shuffle[i] ^= shuffle[j];
    }
}

/**
 * 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();
 */