Mashiro Mashiro - 1 month ago 18
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++){
set1.add(nums1[i]);
}
for(int i=0;i<nums2.length;i++){
if(set1.contains(nums2[i]))
result.add(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;
}


Thanks in advance for any answer or comment.

Answer

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.

Comments