384. Shuffle an Array

O(n) time O(n) space
证明：
任何一个元素a[i]出现在任何一个位置j的概率是1/n
三种情况讨论（直接用情况1足以）：

1. i < j P(i) = ((n - 1) / n) * ((n - 2) / (n - 1)) * … * (j / (j + 1)) * (1 / j) = (j / n) * (1 / j) = P(a[i]之前没放在位置j) * P(a[i]这次放在位置j) = 1 / n
2. i = j P(i) = (j / n) * (1 / j) = 1 / n
3. i > j P(i) = (j / n) * (1 / j) = 1 / n

class Solution {
public:
    Solution(vector<int> nums) : nums(nums) {
        srand((unsigned)time(NULL));
    }

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

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

    vector<int> nums;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * vector<int> param_1 = obj.reset();
 * vector<int> param_2 = obj.shuffle();
 */