class Solution {
vector<int> orig;
public:
Solution(vector<int> nums) {
for(auto &it: nums) this>orig.push_back(it);
}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
return this>orig;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
vector<int> newArr(this>orig.begin(), this>orig.end());
for(int len = newArr.size(); len > 0; len) {
int idx = rand() % len;
swap(newArr[idx], newArr[len1]);
}
return newArr;
}
};
/**
* 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();
*/
C++ solution, seems extremely slow, any better ideas?


@wl5888
I tried several other solutions in C++, the time cost is just about 360ms so far. B.T.W. perhaps your solution is little bit messy.class Solution { private: vector<int> oldArr; public: Solution(vector<int> nums) { oldArr = nums; } /** Resets the array to its original configuration and return it. */ vector<int> reset() { return oldArr; } /** Returns a random shuffling of the array. */ vector<int> shuffle() { vector<int> newArr = oldArr; for(int i = 0, size = newArr.size(); i < size; ++i) swap(newArr[i], newArr[rand()%size]); return newArr; } };

@LHearen said in C++ solution, seems extremely slow, any better ideas?:
B.T.W. perhaps your solution is little bit messy.
But at least it's not wrong like yours :P

@LHearen
Hi.Take [1,2,3] as an example.
In your solution, there are 27 statuses and in fact there are 6 permutations only. 27 is not divisible for 6, so the probabilities are not the same for sure.

@FlyChicken Your contradiction analysis is quite right, sorry about my carelessness. The solution in my last post is what I always use to avoid the worst case in quickSort.
@StefanPochmann Thank you, man. You are not that mean as usual, hahah. Good point!class Solution { private: vector<int> oldArr; public: Solution(vector<int> nums) { oldArr = nums; } /** Resets the array to its original configuration and return it. */ vector<int> reset() { return oldArr; } /** Returns a random shuffling of the array. */ vector<int> shuffle() { vector<int> newArr = oldArr; for(int size = newArr.size(); size; size) swap(newArr[size1], newArr[rand()%size]); return newArr; } };