Monday, October 24, 2016

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();
The question actually tests about how to shuffle an array. One way is to generate a random number from the start of the array to the end, then swap current position with the generate position. Then increment start by 1 and do it again.


public class Solution {

    int[] orig;
    int[] curr;
    int len;
    final Random random;

    public Solution(int[] num) {
        len = num.length;
        orig = num;
        curr = Arrays.copyOf(num, len);
        random = new Random();
    }
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return this.curr = Arrays.copyOf(orig, orig.length);
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for (int i = 0; i < len - 1; i++) {
            int pos = getPos(i, len);
            swap(curr, i, pos);
        }
        return curr;
    }

    private int getPos(int start, int end) {
        return random.nextInt(end - start) + start;
    }

    private void swap(int[] num, int first, int second) {
        int tmp = num[first];
        num[first] = num[second];
        num[second] = tmp;
    }
}


No comments:

Post a Comment