力扣算法-Day13

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;
}

这一期专栏记录将我每天的刷题，希望各位的监督，也希望和各位共勉。

追光的人，终会光芒万丈！！