aboutsummaryrefslogtreecommitdiff
path: root/find_common_element_2_arr.c
blob: b8c632f37f57923c106709f9d7a4b4dcbae62e6e (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
70
71
72
73
74
75
76
77
78
79
80
81
// 2956. Find Common Elements Between Two Arrays
#include "leetcode.h"

/*
 * given two integer arrays 'nums1' and 'nums2' of sizes 'n' and 'm'
 * respectively. calculate the following values: 'answer1' is the number of
 * indices 'i' such that 'nums1[i]' exists in 'nums2' and 'answer2' is the
 * number of indices 'i' such that 'nums2[i]' exist in 'nums1'
 */

typedef struct {
  int val;
  int key;
  UT_hash_handle hh;
} hash_table;

int *findIntersectionValues(int *nums1, int nums1Size, int *nums2,
                            int nums2Size, int *returnSize) {
  hash_table *hash = NULL, *elem, *tmp;
  *returnSize = 2;
  int *ans = (int *)malloc(*returnSize * sizeof(int));
  ans[1] = 0, ans[0] = 0;
  for (int i = 0; i < nums1Size; ++i) {
    HASH_FIND_INT(hash, &nums1[i], elem);
    if (!elem) {
      elem = malloc(sizeof(hash_table));
      elem->key = nums1[i];
      elem->val = 1;
      HASH_ADD_INT(hash, key, elem);
    } else
      elem->val++;
  }
  for (int i = 0; i < nums2Size; i++) {
    HASH_FIND_INT(hash, &nums2[i], elem);
    if (elem) {
      ans[0] += elem->val;
      elem->val = 0;
    }
  }
  HASH_CLEAR(hh, hash);
  for (int i = 0; i < nums2Size; ++i) {
    HASH_FIND_INT(hash, &nums2[i], elem);
    if (!elem) {
      elem = malloc(sizeof(hash_table));
      elem->val = 1;
      elem->key = nums2[i];
      HASH_ADD_INT(hash, key, elem);
    } else
      elem->val++;
  }
  for (int i = 0; i < nums1Size; i++) {
    HASH_FIND_INT(hash, &nums1[i], elem);
    if (elem) {
      ans[1] += elem->val;
      elem->val = 0;
    }
  }
  HASH_CLEAR(hh, hash);
  return ans;
}
int main() {
  int n11[] = {2, 3, 2}, n21[] = {1, 2}, n12[] = {4, 3, 2, 3, 1},
      n22[] = {2, 2, 5, 2, 3, 6}, n13[] = {3, 4, 2, 3}, n23[] = {1, 5};
  int rs1, rs2, rs3;
  int *fiv1 =
      findIntersectionValues(n11, ARRAY_SIZE(n11), n21, ARRAY_SIZE(n21), &rs1);
  int *fiv2 =
      findIntersectionValues(n12, ARRAY_SIZE(n12), n22, ARRAY_SIZE(n22), &rs2);
  int *fiv3 =
      findIntersectionValues(n13, ARRAY_SIZE(n13), n23, ARRAY_SIZE(n23), &rs3);
  for (int i = 0; i < rs1; i++)
    printf("%d ", fiv1[i]); // expect: 2 1
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%d ", fiv2[i]); // expect: 3 4
  printf("\n");
  for (int i = 0; i < rs3; i++)
    printf("%d ", fiv3[i]); // expect: 0 0
  printf("\n");
  free(fiv1), free(fiv2), free(fiv3);
}