题目描述
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
使用哈希进行求解。
C语言版
/** * Note: The returned array must be malloced, assume caller calls free(). */ int _callback(const void* val1, const void* val2) { return *(int*)val1 - *(int*)val2; } int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) { int index1 = 0, index2 = 0; qsort(nums1, nums1Size, sizeof(nums1[0]), _callback); qsort(nums2, nums2Size, sizeof(nums2[0]), _callback); *returnSize = 0; int* ret = (int*)malloc(sizeof(int) * fmin(nums1Size, nums2Size)); while (index1 < nums1Size && index2 < nums2Size) { if (nums1[index1] < nums2[index2]) { index1++; /*如果nums1中的数据小，那么nums1的游标下移*/ } else if (nums1[index1] > nums2[index2]) { index2++; /*如果nums2中的数据小，那么nums2的游标下移*/ } else { *(ret + (*returnSize)) = nums1[index1]; /*两个数相等则加入容器*/ index1++; index2++; (*returnSize)++; } } return ret; }
C++版
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> flag; vector<int> ret; for (vector<int>::iterator it = nums1.begin(); it != nums1.end(); it++) { if (flag.find(*it) == flag.end()) { flag.insert(make_pair(*it, 1)); } else { flag[*it]++; } } for (vector<int>::iterator it = nums2.begin(); it != nums2.end(); it++) { if (flag.find(*it) != flag.end()) { if (flag[*it] > 0) { ret.push_back(*it); flag[*it]--; } } } return ret; } };
Python版
#使用哈希记录nums1元素及元素出现的次数，并在nums2中找同时出现的元素存入列表 #时间复杂度 O(m+n) class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: hashmap = {} ret = [] if len(nums1) > len(nums2): return self.intersect(nums2, nums1) for i in nums1: if hashmap.get(i) == None: hashmap[i] = 1 else: hashmap[i] += 1 for i in nums2: if hashmap.get(i) != None: if hashmap[i] > 0: ret.append(i) hashmap[i] -= 1 return ret
