力扣算法-Day13
2023-12-28 13:21:58
349. 两个数组的交集
给定两个数组?nums1
?和?nums2
?,返回?它们的交集?。输出结果中的每个元素一定是?唯一?的。我们可以?不考虑输出结果的顺序?。
提示:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
思路:
暴力解:
? ? ? ? 显而易见的,都会想到用两个循环去寻找寻找公共集合。如果nums1.length = m;nums2.length = n;那时间复杂度O(m*n)。
????????????????如果m、n比较大的话,效率是比较慢的。
哈希表:
? ? ? ? 因为题目中提示中写道:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
所以,我们就可以考虑使用哈希表了,如果说没有这个范围限制,我们就可以去使用暴力解或者自己构建一个哈希表相当于C++中的set集合。
哈希表能解决什么问题呢,一般哈希表都是用来快速判断一个元素是否出现集合里。
暴力解:
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int* result = (int*)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));
if (result == NULL) {
*returnSize = 0;
return NULL;
}
int i, j, k;
int count = 0;
for (i = 0; i < nums1Size; i++) {
for (j = 0; j < nums2Size; j++) {
if (nums1[i] == nums2[j]) {
for (k = 0; k < count; k++) {
if (result[k] == nums1[i]) {
break;
}
}
if (k == count) {
result[count++] = nums1[i];
}
break;
}
}
}
*returnSize = count;
return result;
}
哈希表:(数组)
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int record1[1001] = {0};
int record2[1001] = {0};
for (int i=0; i< nums1Size ; i++) {
record1[nums1[i]]++;
}
for (int i=0; i<nums2Size; i++) {
record2[nums2[i]]++;
}
int count = 0;
int *returned = (int*)malloc(sizeof(int)*nums1Size);
for (int i=0; i<1001; i++) {
if (record1[i] != 0 && record2[i] !=0) {
returned[count] = i;
count++;
}
}
*returnSize = count;
return returned;
}
?构建哈希表:
typedef struct {
int key;
int visited;
} HashTable;
int compare(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable) * nums1Size);
int* result = (int*)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));
if (hashTable == NULL || result == NULL) {
*returnSize = 0;
return NULL;
}
int i, j, count = 0;
for (i = 0; i < nums1Size; i++) {
hashTable[i].key = nums1[i];
hashTable[i].visited = 0;
}
qsort(nums2, nums2Size, sizeof(int), compare);
for (i = 0; i < nums2Size; i++) {
if (i > 0 && nums2[i] == nums2[i-1]) {
continue;
}
for (j = 0; j < nums1Size; j++) {
if (hashTable[j].visited == 0 && nums2[i] == hashTable[j].key) {
result[count++] = nums2[i];
hashTable[j].visited = 1;
break;
}
}
}
free(hashTable);
*returnSize = count;
return result;
}
这一期专栏记录将我每天的刷题,希望各位的监督,也希望和各位共勉。
追光的人,终会光芒万丈!!
文章来源:https://blog.csdn.net/m0_73771309/article/details/135258122
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!