leetcode 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();

题目地址：leetcode Shuffle an Array

题意：给定一个数组，实现两个接口 reset() 和 shuffle()，前者为置位返回初始的数组，后者为随机化数组。

思路：用swap，每次从[i,n-1]中随机一个数，和第i个数交换即可。

Python code如下：

class Solution(object):
    def __init__(self, nums):
        """
        :type nums: List[int]
        :type size: int
        """
        self.nums = nums
        self.output = nums[:]

    def reset(self):
        """
        Resets the array to its original configuration and return it.
        :rtype: List[int]
        """
        self.output = self.nums[:]
        return self.nums

    def shuffle(self):
        """
        Returns a random shuffling of the array.
        :rtype: List[int]
        """
        n = len(self.output)
        for i in xrange(n):
            _id = random.randint(i, n - 1)
            self.output[i], self.output[_id] = self.output[_id], self.output[i]
        return self.output

当然，上面的代码是每次洗牌从上一次的结果继续进行的，这也符合我们对于洗牌的感觉。

如果每次从初始数组进行洗牌，那么reset数组只需要返回初始数组。。

class Solution(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        :type size: int
        """
        self.nums = nums

    def reset(self):
        """
        Resets the array to its original configuration and return it.
        :rtype: List[int]
        """
        return self.nums

    def shuffle(self):
        """
        Returns a random shuffling of the array.
        :rtype: List[int]
        """
        output = self.nums[:]
        n = len(output)
        for i in xrange(n):
            _id = random.randint(i,n-1)
            output[i],output[_id] = output[_id],output[i]
        return output

其他的代码：

C++

class Solution {
	vector<int> nums;
	vector<int> output;
public:
	Solution(vector<int> nums) :nums(nums),output(nums) {}

	/** Resets the array to its original configuration and return it. */
	vector<int> reset() {
		return output = nums;
	}

	/** Returns a random shuffling of the array. */
	vector<int> shuffle() {
		int n = output.size();
		for (int i = 0; i < n; i++) {
			int _id = rand() % (n - i);
			swap(output[i], output[i + _id]);
		}
		return output;
	}
};

Java

public class Solution {
    private int[] nums;
    private int[] output;
    private Random random;
    
    public Solution(int[] nums) {
        this.nums = nums;
        this.output = Arrays.copyOf(nums,nums.length);
        this.random = new Random();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return this.output = Arrays.copyOf(nums,nums.length);
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int n = output.length;
		for (int i = 0; i < n; i++) {
			int _id = random.nextInt(n-i);
			int temp = output[i];
			output[i] = output[i+_id];
			output[i+_id] = temp;
		}
		return output;
    }
}

本题是leetcode 384 Shuffle an Array 的题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/