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();
//https://discuss.leetcode.com/topic/54022/c-solution-with-fisher-yates-algorithm/6
class Solution {
vector<int> arr, idx;
public:
Solution(vector<int> nums) {
srand(time(NULL));
arr.resize(nums.size());
idx.resize(nums.size());
;i<nums.size();i++){
arr[i] = nums[i];
idx[i] = nums[i];
}
}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
;i<arr.size();i++)
arr[i] = idx[i];
return arr;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
int i,j;
; i > ; i--) {
j = rand() % (i + );
swap(arr[i], arr[j]);
}
return arr;
}
};
//C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef struct
{
int size;
int *BaseNum;
int *RandNum;
}Solution;
Solution* solutionCreate(int* nums, int size)
{
Solution* solu;
solu = (Solution*)malloc(sizeof (Solution));
solu->size = size;
solu->BaseNum = (int *)malloc(sizeof(int)*size);
solu->RandNum = (int *)malloc(sizeof(int)*size);
memcpy(solu->BaseNum, nums, sizeof(int)*size);
memcpy(solu->RandNum, nums, sizeof(int)*size);
solu->size = size;
return solu;
}
int* solutionReset(Solution* obj,int *returnSize) {
return obj->BaseNum;
}
int* solutionShuffle(Solution* obj,int *returnSize) {
int i,j,k;
int temp[obj->size];
srand((unsigned int)time(NULL));
j = ;
while (j < obj->size)
{
temp[j] = rand()%obj->size;
;i<j;i++)
{
if (temp[i] == temp[j]||temp[j] == obj->size)
break;
}
if (i<j)
continue;
j++;
}
;k < obj->size;k++)
{
//printf ("%d\t",temp[k]);
obj->RandNum[k] = obj->BaseNum[temp[k]];
}
return obj->RandNum;
}
void solutionFree(Solution* obj) {
if(obj->BaseNum != NULL){
free(obj->BaseNum);
obj->BaseNum = NULL;
}
if(obj->RandNum != NULL){
free(obj->RandNum);
obj->RandNum = NULL;
}
obj->size = ;
if(obj != NULL){
free(obj);
obj = NULL;
}
}
/**
* Your Solution struct will be instantiated and called as such:
* struct Solution* obj = solutionCreate(nums, size);
* int* param_1 = solutionReset(obj);
* int* param_2 = solutionShuffle(obj);
* solutionFree(obj);
*/
int main(void) {
//freopen("../tmp", "r", stdin);
Solution *st;
];
int size;
scanf("%d", &size);
//getchar();
; i < size; ++i) {
scanf("%d", &nums[i]);
}
st = solutionCreate(nums, size);
int *p1 = solutionReset(st, &size);
printf("the orignal:");
; i < size; ++i) {
printf("%d ", *p1);
p1++;
}
printf("\n");
int *p2 = solutionShuffle(st, &size);
printf("after shuffle:");
; i < size; ++i) {
printf("%d ", *p2);
p2++;
}
printf("\n");
if(st != NULL){
solutionFree(st);
}
;
}