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); } ; }