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:
- 3ms, 35.79
- Hash the shorter array, maybe useful, maybe not.
- Delete during checking the longer array.
- The difference between python and c.
LeetCode: 349. Intersection of Two Arrays





近期评论