Mashiro - 1 year ago 96
C Question

# leetcode 349: Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

Each element in the result must be unique.

The result can be in any order.

I first use two loops to solve this problem, and the RunTime Error pops up beacuse the complexity is O(n ^ 2). Then, I look up many solutions, but none of them is written in C. However, I find a solution in C++ using hashset and this solution is O(m + n) complexity.

The solution is here:

``````public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1.length==0||nums2.length==0)
return new int[0];
Set<Integer> result = new HashSet();
Set<Integer> set1 = new HashSet();
for(int i=0;i<nums1.length;i++){
}
for(int i=0;i<nums2.length;i++){
if(set1.contains(nums2[i]))
}
int[] res = new int[result.size()];
int i=0;
Iterator iter = result.iterator();
while(iter.hasNext()){
res[i++]=(int)iter.next();
}
return res;
}
}
``````

I want to use hashtable in C, so I define a hashtable struct myself and write a hashFind function to find whether the value is in the hashtable. But, RunTime Error still pops up. I want to ask if the problem stems from my hashFind function? But, I think that since I define a enough large size of hashtable and the given data from leetcode is not that large, the complexity of my algorithm should be O(m + n) too.

Here is my code:

``````/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
#define HASHSIZE 1007

static int hashf(int key) {
return key % HASHSIZE;
}

typedef struct listnode {
int val;
struct listnode *next;
} listnode;

typedef struct hashtable {
listnode **hash;
} hashtable;

static hashtable *hashCreat(void) {
hashtable *h;
int i;

if ((h = (hashtable *) malloc(sizeof(hashtable))) == NULL) return NULL;
if ((h->hash = (listnode **) malloc(sizeof(listnode *) * HASHSIZE)) == NULL) return NULL;
for (i = 0; i < HASHSIZE; i++)
h->hash[i] = NULL;
return h;
}

static void hashRelease(hashtable *h) {
listnode *current, *tmp;
int i;

for (i = 0; i < HASHSIZE; i++) {
current = h->hash[i];
while (current != NULL) {
tmp = current->next;
free(current);
current = tmp;
}
}
free(h->hash);
free(h);
}

static void hashInsert(hashtable *h, int key) {
int value;
listnode *node;
listnode *current;

if ((node = (listnode *) malloc(sizeof(listnode))) ==NULL) return NULL;
value = hashf(key);
current = h->hash[value];
while (current != NULL) {
if (current->val == key) return;
current = current->next;
}
node->next = h->hash[value];
h->hash[value] = node;
node->val = key;
}

static bool hashFind(hashtable *h, int key) {
int value;
listnode *current;

value = hashf(key);
current = h->hash[value];
while (current != NULL) {
if (current->val = key) return 1;
current = current->next;
}
return 0;
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
if (nums1Size == 0 || nums2Size == 0) return NULL;

int *result;
int i, j;
int pos;
hashtable *h;

if ((result = (int *) malloc(sizeof(int) * *returnSize)) ==NULL) return NULL;
h = hashCreat();
pos = 0;
for (i = 0; i < nums1Size; i++)
hashInsert(h, nums1[i]);
for (j = 0; j < nums2Size; j++)
if (hashFind(h, nums2[j]))
result[pos++] = nums2[j];
hashRelease(h);
return result;
}
``````

Runtime Error means your code didn't execute and exit properly during runtime. Its not about time complexity(TLE - time limit exceeded) or space complxity(MLE - memory limit exceeded). There are many reasons of runtime error. Among those, most frequent one for Leetcode problems are - `array out of bound`. May be your are trying to access some index of your container which is out of bound.

Here is the modified and Accepted solution of yours:

``````/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
#define HASHSIZE 1007

static int hashf(int key) {
return key % HASHSIZE;
}

typedef struct listnode {
int val;
struct listnode *next;
} listnode;

typedef struct hashtable {
listnode **hash;
} hashtable;

static hashtable *hashCreat(void) {
hashtable *h;
int i;

if ((h = (hashtable *) malloc(sizeof(hashtable))) == NULL) return NULL;
if ((h->hash = (listnode **) malloc(sizeof(listnode *) * HASHSIZE)) == NULL) return NULL;
for (i = 0; i < HASHSIZE; i++)
h->hash[i] = NULL;
return h;
}

static void hashRelease(hashtable *h) {
listnode *current, *tmp;
int i;

for (i = 0; i < HASHSIZE; i++) {
current = h->hash[i];
while (current != NULL) {
tmp = current->next;
free(current);
current = tmp;
}
}
free(h->hash);
free(h);
}

static void hashInsert(hashtable *h, int key) {
int value;
listnode *node;
listnode *current;

// if ((node = (listnode *) malloc(sizeof(listnode))) ==NULL) return NULL;
// Correction: You can't return NULL from a void function
if ((node = (listnode *) malloc(sizeof(listnode))) ==NULL) return;
value = hashf(key);
current = h->hash[value];
while (current != NULL) {
if (current->val == key) return;
current = current->next;
}
node->next = h->hash[value];
h->hash[value] = node;
node->val = key;
}

static bool hashFind(hashtable *h, int key) {
int value;
listnode *current;

value = hashf(key);
current = h->hash[value];
while (current != NULL) {
// if (current->val = key) return 1;
// Correction: == instead of =
if (current->val == key) return 1;
current = current->next;
}
return 0;
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
if (nums1Size == 0 || nums2Size == 0) return NULL;

int* result;
int i, j;
int pos;
hashtable *h;
// you need another hash to check if intersection array is including duplicate elements
hashtable *h2;

// if ((result = (int *) malloc(sizeof(int) * *returnSize)) ==NULL) return NULL;
// Correction: returnSize is the size of result array you have to return. Allocate minimum of two input array length as intersection array can't be bigger than smaller array
int minLength = (nums1Size < nums2Size ? nums1Size : nums2Size);
if ((result = (int *) malloc(sizeof(int) * (minLength + 1))) ==NULL) return NULL;
h = hashCreat();
h2 = hashCreat();
pos = 0;
for (i = 0; i < nums1Size; i++)
hashInsert(h, nums1[i]);
for (j = 0; j < nums2Size; j++)
if (hashFind(h, nums2[j])) {
// check if current element is already included or not
if(!hashFind(h2, nums2[j])) {
result[pos++] = nums2[j];
hashInsert(h2, nums2[j]);
}
}
hashRelease(h);
hashRelease(h2);

*returnSize = pos; // set the result array size which will be returned to caller as pass by reference
return result;
}
``````

The fact is - you won't get the chance to implement your own hashtable in interview. So you should learn and use some high level language like C++ which has these data-structure in standard library.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download