From e8c6049f79e0102afa0917cca08062232d465650 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 30 Dec 2024 22:28:47 +0100 Subject: 384. shuffle an array --- shuffle_an_array.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++ shuffle_an_array.py | 22 ++++++++++++++++ shuffle_array.c | 31 ----------------------- shuffle_array.cpp | 39 ----------------------------- shuffle_the_array.c | 31 +++++++++++++++++++++++ shuffle_the_array.cpp | 39 +++++++++++++++++++++++++++++ 6 files changed, 161 insertions(+), 70 deletions(-) create mode 100644 shuffle_an_array.c create mode 100644 shuffle_an_array.py delete mode 100644 shuffle_array.c delete mode 100644 shuffle_array.cpp create mode 100644 shuffle_the_array.c create mode 100644 shuffle_the_array.cpp diff --git a/shuffle_an_array.c b/shuffle_an_array.c new file mode 100644 index 0000000..54a0ddd --- /dev/null +++ b/shuffle_an_array.c @@ -0,0 +1,69 @@ +// 384. Shuffle an Array +#include "leetcode.h" + +/* + * given an integer array 'nums', design an algorithm to randomly shuffle the + * array. all permutations of the array should be equally likely as a result of + * the shuffling. implement the 'Solution' class: 'Solution(int[] nums)' + * initialises the object with the integer array 'nums' 'int[] reset()' resets + * the array to its original configuration and returns it 'int[] shuffle()' + * return a random shuffling of the array + */ + +typedef struct { + int *original; + int *nums; + int size; +} Solution; + +Solution *solutionCreate(int *nums, int numsSize) { + Solution *obj = (Solution *)malloc(sizeof(Solution)); + obj->original = (int *)malloc(numsSize * sizeof(int)); + obj->nums = (int *)malloc(numsSize * sizeof(int)); + obj->size = numsSize; + memcpy(obj->original, nums, numsSize * sizeof(int)); + memcpy(obj->nums, nums, numsSize * sizeof(int)); + return obj; +} + +int *solutionReset(Solution *obj, int *retSize) { + *retSize = obj->size; + memcpy(obj->nums, obj->original, obj->size * sizeof(int)); + return obj->original; +} + +int *solutionShuffle(Solution *obj, int *retSize) { + *retSize = obj->size; + for (int i = 0; i < obj->size; i++) { + int tmp = obj->nums[i]; + int pos = rand() % obj->size; + obj->nums[i] = obj->nums[pos]; + obj->nums[pos] = tmp; + } + return obj->nums; +} + +void solutionFree(Solution *obj) { + free(obj->nums); + free(obj->original); + free(obj); +} + +int main() { + int n1[] = {1, 2, 3}, rs1, rs2, rs3; + Solution *obj = solutionCreate(n1, ARRAY_SIZE(n1)); + int *ss1 = solutionShuffle(obj, &rs1); + int *sr1 = solutionReset(obj, &rs2); + int *ss2 = solutionShuffle(obj, &rs3); + for (int i = 0; i < rs1; i++) + printf("%d ", ss1[i]); // expect: 3 1 2 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", sr1[i]); // expect: 1 2 3 + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%d ", ss2[i]); // expect: 1 3 2 + printf("\n"); + free(ss1), free(sr1), free(ss2); + solutionFree(obj); +} diff --git a/shuffle_an_array.py b/shuffle_an_array.py new file mode 100644 index 0000000..5b94f3c --- /dev/null +++ b/shuffle_an_array.py @@ -0,0 +1,22 @@ +# 384. Shuffle an Array +from random import sample + +""" +given an integer array 'nums', design an algorithm to randomly shuffle the +array. all permutations of the array should be equally likely as a result of +the shuffling. implement the 'Solution' class: 'Solution(int[] nums)' +initialises the object with the integer array 'nums' 'int[] reset()' resets +the array to its original configuration and returns it 'int[] shuffle()' +return a random shuffling of the array +""" + + +class Solution(list): + reset, shuffle = list, lambda x: sample(x, len(x)) + + +if __name__ == "__main__": + obj = Solution([1, 2, 3]) + print(obj.shuffle()) + print(obj.reset()) + print(obj.shuffle()) diff --git a/shuffle_array.c b/shuffle_array.c deleted file mode 100644 index 0192604..0000000 --- a/shuffle_array.c +++ /dev/null @@ -1,31 +0,0 @@ -// 1470. Shuffle the Array -#include -#include - -/* - * given array 'nums' consisting of '2n' elements in the form - * [x1, x2, ..., xn, y1, y2, ..., yn] - * return the array in the form [x1, y1, x2, y2, ..., xn, yn] - */ - -int *shuffle(int *nums, int numsSize, int n, int *returnSize) { - int i = 0, j = n, k = 0; - int *ans = (int *)malloc(numsSize * sizeof(int)); - while (i < n && j < numsSize) { - ans[k++] = nums[i]; - ans[k++] = nums[j]; - i++; - j++; - } - *returnSize = numsSize; - return ans; -} - -int main() { - int nums1[] = {2, 5, 1, 3, 4, 7}, rs1[] = {6}, ns1 = 6, n1 = 3; - int nums2[] = {1, 2, 3, 4, 4, 3, 2, 1}, rs2[] = {8}, ns2 = 8, n2 = 4; - int nums3[] = {1, 1, 2, 2}, rs3[] = {4}, ns3 = 4, n3 = 2; - printf("%d\n", *shuffle(nums1, ns1, n1, rs1)); - printf("%d\n", *shuffle(nums2, ns2, n2, rs2)); - printf("%d\n", *shuffle(nums3, ns3, n3, rs3)); -} diff --git a/shuffle_array.cpp b/shuffle_array.cpp deleted file mode 100644 index f7dddea..0000000 --- a/shuffle_array.cpp +++ /dev/null @@ -1,39 +0,0 @@ -// 1470. Shuffle the Array -#include "leetcode.h" - -/* - * given array 'nums' consisting of '2n' elements in the form - * [x1, x2, ..., xn, y1, y2, ..., yn] - * return the array in the form [x1, y1, x2, y2, ..., xn, yn] - */ - -class Solution { -public: - vector shuffle(vector &nums, int n) { - int len = nums.size(); - for (int i = n; i < len; i++) - nums[i] = (nums[i] << 10) | nums[i - n]; - int idx = 0; - for (int i = n; i < len; i++, idx += 2) { - nums[idx] = nums[i] & 1023; - nums[idx + 1] = nums[i] >> 10; - } - return nums; - } -}; - -int main() { - Solution obj; - vector nums1 = {2, 5, 1, 3, 4, 7}; - vector nums2 = {1, 2, 3, 4, 4, 3, 2, 1}; - vector nums3 = {1, 1, 2, 2}; - for (auto i : obj.shuffle(nums1, 3)) - cout << i << ' '; // expect: 2,3,5,4,1,7 - cout << endl; - for (auto i : obj.shuffle(nums2, 4)) - cout << i << ' '; // expect: 1,4,2,3,3,2,4,1 - cout << endl; - for (auto i : obj.shuffle(nums3, 2)) - cout << i << ' '; // expect: 1,2,1,2 - cout << endl; -} diff --git a/shuffle_the_array.c b/shuffle_the_array.c new file mode 100644 index 0000000..0192604 --- /dev/null +++ b/shuffle_the_array.c @@ -0,0 +1,31 @@ +// 1470. Shuffle the Array +#include +#include + +/* + * given array 'nums' consisting of '2n' elements in the form + * [x1, x2, ..., xn, y1, y2, ..., yn] + * return the array in the form [x1, y1, x2, y2, ..., xn, yn] + */ + +int *shuffle(int *nums, int numsSize, int n, int *returnSize) { + int i = 0, j = n, k = 0; + int *ans = (int *)malloc(numsSize * sizeof(int)); + while (i < n && j < numsSize) { + ans[k++] = nums[i]; + ans[k++] = nums[j]; + i++; + j++; + } + *returnSize = numsSize; + return ans; +} + +int main() { + int nums1[] = {2, 5, 1, 3, 4, 7}, rs1[] = {6}, ns1 = 6, n1 = 3; + int nums2[] = {1, 2, 3, 4, 4, 3, 2, 1}, rs2[] = {8}, ns2 = 8, n2 = 4; + int nums3[] = {1, 1, 2, 2}, rs3[] = {4}, ns3 = 4, n3 = 2; + printf("%d\n", *shuffle(nums1, ns1, n1, rs1)); + printf("%d\n", *shuffle(nums2, ns2, n2, rs2)); + printf("%d\n", *shuffle(nums3, ns3, n3, rs3)); +} diff --git a/shuffle_the_array.cpp b/shuffle_the_array.cpp new file mode 100644 index 0000000..f7dddea --- /dev/null +++ b/shuffle_the_array.cpp @@ -0,0 +1,39 @@ +// 1470. Shuffle the Array +#include "leetcode.h" + +/* + * given array 'nums' consisting of '2n' elements in the form + * [x1, x2, ..., xn, y1, y2, ..., yn] + * return the array in the form [x1, y1, x2, y2, ..., xn, yn] + */ + +class Solution { +public: + vector shuffle(vector &nums, int n) { + int len = nums.size(); + for (int i = n; i < len; i++) + nums[i] = (nums[i] << 10) | nums[i - n]; + int idx = 0; + for (int i = n; i < len; i++, idx += 2) { + nums[idx] = nums[i] & 1023; + nums[idx + 1] = nums[i] >> 10; + } + return nums; + } +}; + +int main() { + Solution obj; + vector nums1 = {2, 5, 1, 3, 4, 7}; + vector nums2 = {1, 2, 3, 4, 4, 3, 2, 1}; + vector nums3 = {1, 1, 2, 2}; + for (auto i : obj.shuffle(nums1, 3)) + cout << i << ' '; // expect: 2,3,5,4,1,7 + cout << endl; + for (auto i : obj.shuffle(nums2, 4)) + cout << i << ' '; // expect: 1,4,2,3,3,2,4,1 + cout << endl; + for (auto i : obj.shuffle(nums3, 2)) + cout << i << ' '; // expect: 1,2,1,2 + cout << endl; +} -- cgit v1.2.3