讨论/《哈希表》 - 两个数组的交集/
《哈希表》 - 两个数组的交集
共 7 个回复
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //创建哈希集合
        unordered_set<int> hashset;
        //创建返回数组
        vector<int> result;
        //遍历赋值
        for(auto val : nums1){
            hashset.insert(val);
        }
        //遍历叉值,相同压入vector,并再哈希集合中删除
        for(auto val : nums2){
            if(hashset.count(val) > 0){
                result.push_back(val);
                hashset.erase(val);
            }
        }
        return result;
    }
};
3

JavaScript版本~

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const set = new Set(nums1)
    let result = []
    nums2.forEach(num => {
        if(set.has(num) && !result.includes(num)) result.push(num)
    })
    return result
};
2

执行用时:8 ms, 在所有 C++ 提交中击败了63.15%的用户
内存消耗:10.1 MB, 在所有 C++ 提交中击败了70.06%的用户

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> hashset;
        vector<int> result;
        for(int i = 0; i < nums1.size();i++)
        {
            if(!hashset.count(nums1[i]))
                hashset.insert(nums1[i]);
        }
        for(int i = 0; i < nums2.size();i++)
        {
            if(hashset.count(nums2[i]))
               result.push_back(nums2[i]);
               hashset.erase(nums2[i]); 
        }
        return result;
    }
};

你这代码长度也太吓人了

#define MAX_NUM 100000

typedef struct {
    int key;
    int flag;
    UT_hash_handle hh;
}HashTable;

HashTable *g_users;
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    /* 异常保护 */
    if ((nums1 == NULL) || (nums2 == NULL) || (nums1Size == 0) || (nums2Size == 0)) {
        *returnSize = 0;
        return NULL;
    }
    g_users = NULL;
    for (int i = 0; i < nums1Size; i++) {
        HashTable *cur = NULL;
        HASH_FIND_INT(g_users, nums1 + i, cur);
        if (cur == NULL) {
            cur = (HashTable *)malloc(sizeof(HashTable));
            cur->key = *(nums1 + i);
            /* 设置标志位 */
            cur->flag = 0;
            HASH_ADD_INT(g_users, key, cur);
            continue;
        }
    }
    int *r = (int *)malloc(sizeof(int) * MAX_NUM);
    memset(r, 0x00, sizeof(int) * MAX_NUM);
    int index = 0;
    for (int i = 0; i < nums2Size; i++) {
        HashTable *cur = NULL;
        HASH_FIND_INT(g_users, nums2 + i, cur);
        if (cur == NULL) {
            continue;
        }
        if (cur->flag == 0) {
            r[index++] = cur->key;
            /* 已经检测到重复的数字,设置标志位 */
            cur->flag = 1;
        }
    }
    int *rslt = (int *)malloc(sizeof(int) * index);
    memset(rslt, 0x00, sizeof(int) * index);
    memcpy(rslt, r, sizeof(int) * index);
    *returnSize = index;
    free(r);
    HashTable *tmp = NULL;
    HashTable *s = NULL;
    /* 清空哈希表 */
    HASH_ITER(hh, g_users, s, tmp) {
        HASH_DEL(g_users, s);
        free(s);
    }
    return rslt;
}

想保证nums1是长度较小的那个

public int[] getIntersection(Set<Integer> set1,Set<Integer> set2){
if(set1.size()>set2.size()){
return getIntersection(set2,set1);
}

菜鸟问一下这个啥意思,不是很懂为什么把他交换顺序