P58 随机洗牌

描述#

这个题目说的是，给你一个整数数组表示一副牌，你要写一个随机洗牌函数来返回这个数组的一个排列。并且要保证每次返回的排列都是等概率的。假设已经给你一个完美的随机数生成器。

代码#

public class AlgoCasts {

  private Random rnd = new Random();

  void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }

  // Time: O(n), Space: O(1)
  public int[] shuffle(int[] nums) {
    for (int i = nums.length - 1; i > 0; --i) {
      int j = rnd.nextInt(i+1);
      swap(nums, i, j);
    }
    return nums;
  }

}