aboutsummaryrefslogtreecommitdiff
path: root/shuffle_an_array.c
blob: 54a0ddd005a9d3d6e4eca209f0f8238e52cb940a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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);
}