PU Intersection of Two Arrays

Jan 01, 1970

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

  • Each element in the result must be unique.
  • The result can be in any order.

Example:

  • Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

C Solution:

struct HE {
    int val;
    struct HE *next;
};
struct HT {
    int size;
    struct HE **list;
};
struct HT *createHT() {
    struct HT *ht = malloc(sizeof(struct HT));
    ht->size = 1024;
    ht->list = calloc(ht->size, sizeof(struct HE *));
    return ht;
}
void insertHT(struct HT *ht, int val) {
    int ind = val % ht->size;
    struct HE *p = ht->list[ind];
    while (p) {
        if (p->val == val) return;
        else p = p->next;
    }
    struct HE *he = malloc(sizeof(struct HE));
    he->val = val;
    he->next = ht->list[ind];
    ht->list[ind] = he;
}
bool findHT(struct HT *ht, int val) {
    int ind = val % ht->size;
    struct HE **p = &(ht->list[ind]);
    while (*p) {
        if ((*p)->val == val) {
            struct HE *tmp = (*p)->next;
            free(*p);
            *p = tmp;
            return true;
        }
        *p = (*p)->next;
    }
    return false;
}
void save(int **res, int *size, int *returnSize, int val) {
    if (*size == *returnSize) {
        *size += 1000;
        *res = realloc(*res, *size * sizeof(int));
    }
    (*res)[(*returnSize)++] = val;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    if (nums1Size < 1 || nums2Size < 1) return 0;
    int *shorter, *longer, ssize, lsize;
    if (nums1Size < nums2Size) {
        shorter = nums1;
        longer = nums2;
        ssize = nums1Size;
        lsize = nums2Size;
    }
    else {
        shorter = nums2;
        longer = nums1;
        ssize = nums2Size;
        lsize = nums1Size;
    }
    int size = 1000;
    int *res = malloc(ssize * sizeof(int));
    *returnSize = 0;
    struct HT *ht = createHT();
    int i;
    for (i = 0; i < ssize; i++) {
        insertHT(ht, shorter[i]);
    }
    for (i = 0; i < lsize; i++) {
        if (findHT(ht, longer[i])) {
            save(&res, &size, returnSize, longer[i]);
        }
    }
    return res;
}

Python Solution:

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        return list(set(nums1) & set(nums2))

Summary:

  1. 3ms, 35.79
  2. Hash the shorter array, maybe useful, maybe not.
  3. Delete during checking the longer array.
  4. The difference between python and c.

LeetCode: 349. Intersection of Two Arrays