384.Shuffle-an-Array

384. Shuffle an Array

题目地址

https://leetcode.com/problems/shuffle-an-array/

题目描述

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

代码

Approach #1

class Solution {
    private int[] array;
  private int[] original;
  private Random rand = new Random();

  public Solution(int[] nums) {
        array = nums;
    original = nums.clone();
  }

  /** Resets the array to its original configuration and return it. */
  public int[] reset() {
        array = original;
    original = original.clone();
    return array;
  }

  /** Returns a random shuffling of the array. */
  public int[] shuffle() {
        List<Integer> aux = getArrayCopy();
    for (int i = 0; i < array.length; i++) {
      int removeIdx = rand.nextInt(aux.size());
      array[i] = aux.get(removeIdx);
      aux.remove(removeIdx);
    }
    return array;
  }

   private List<Integer> getArrayCopy() {
        List<Integer> asList = new ArrayList<Integer>();
        for (int i = 0; i < array.length; i++) {
            asList.add(array[i]);
        }
        return asList;
    }
}

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

Approach #2 Fisher-Yates Algorithm

class Solution {
    private int[] array;
    private int[] original;
    Random rand = new Random();

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }

    public int[] reset() {
        array = original;
        original = original.clone();
        return original;
    }

    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) {
            swap(i, rand.nextInt(array.length - i) + i);
        }
        return array;
    }

     private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}