C solution with HashMap,3ms


  • 0
    W
    #define MAP_SIZE 1000
    struct HashMap
    {
    	int count;
    	int count1;
    	int val;
    	struct HashMap *next;
    } disHashMap[MAP_SIZE];
    
    
    void addToHashMap(int key,int flag) {
    	int slot = abs(key % MAP_SIZE);
    	struct HashMap *p;
        if(flag==1){
    		if (disHashMap[slot].val == key) {
    			disHashMap[slot].count++;
    		} else if (disHashMap[slot].val == 0) {
    			disHashMap[slot].val = key;
    			disHashMap[slot].count++;
    		} else {
    			p = &disHashMap[slot];
    			while (p->val != key && p->next != NULL) {
    				p = p->next;
    			}
    			if (p->val == key) {
    				p->count++;
    			} else {
    				p->next = (struct HashMap *)malloc(sizeof(struct HashMap));
    				p = p->next;
    				p->val = key;
    				p->count = 1;
                    p->count1 = 0;
    				p->next = NULL;
    			}
    		}
    	}
    	else if(flag==2){
    		if (disHashMap[slot].val == key) {
    			disHashMap[slot].count1++;
    		} else if (disHashMap[slot].val == 0) {
    			disHashMap[slot].val = key;
    			disHashMap[slot].count1++;
    		} else {
    			p = &disHashMap[slot];
    			while (p->val != key && p->next != NULL) {
    				p = p->next;
    			}
    			if (p->val == key) {
    				p->count1++;
    			} else {
    				p->next = (struct HashMap *)malloc(sizeof(struct HashMap));
    				p = p->next;
    				p->val = key;
    				p->count1 = 1;
                    p->count = 0;
    				p->next = NULL;
    			}
    		}
    	}
    
    }
    
    int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    	struct HashMap *p=NULL;
    	for (int k = 0; k < MAP_SIZE; k++) {
    		disHashMap[k].val = 0;
    		disHashMap[k].count = 0;
                    disHashMap[k].count1 = 0;
    		disHashMap[k].next = NULL;
    	}    
    	for(int i=0;i<nums1Size;i++){
    		addToHashMap(nums1[i],1);
    	}
    	for(int j=0;j<nums2Size;j++){
    		addToHashMap(nums2[j],2);
    	}
    	int count=0;
    	int *returnArray=NULL;
    	for (int k = 0; k < MAP_SIZE; k++) {
    		p = &disHashMap[k];
    		while (p != NULL) {
    			int tmp=p->count<p->count1?p->count:p->count1;
    			if (tmp>0) {
    				count+=tmp;
    				returnArray=realloc(returnArray,count*sizeof(int));
    				for(int i=0;i<tmp;i++){
    					returnArray[count-i-1]=p->val;
    				}
    			}
    			p = p->next;
    		}		
    	}   
    	*returnSize=count;
    	return returnArray; 	
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.