C solution with hashMap,beat 100%,80ms


  • 0
    W

    *This solution was figured out by @yaoxinghui ,and i changed the MAP_SIZE from 500 to 1000,i found it faster!

    #define MAP_SIZE 1000
    struct HashMap
    {
    	int count;
    	int val;
    	struct HashMap *next;
    } disHashMap[MAP_SIZE];
    
    
    void addToHashMap(int key) {
    	int slot = key % MAP_SIZE;
    	struct HashMap *p;
    
    	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->next = NULL;
    		}
    	}
    
    }
    int getDistance(int* a, int *b) {
    	return abs(a[0] - b[0]) * abs(a[0] - b[0]) + abs(a[1] - b[1]) * abs(a[1] - b[1]);
    }
    int numberOfBoomerangs(int** points, int pointsRowSize, int pointsColSize) {
    	int i, j, k;
    	int ret = 0;
    	struct HashMap *p, *toBeFree, *next;
    	for (i = 0; i < pointsRowSize; i++) {
    		for (k = 0; k < MAP_SIZE; k++) {
    			disHashMap[k].val = 0;
    			disHashMap[k].count = 0;
    			disHashMap[k].next = NULL;
    		}
    		for (j = 0; j < pointsRowSize; j++) {
    			if (i == j) {
    				continue;
    			}
    			addToHashMap(getDistance(points[i], points[j]));
    		}
    		for (k = 0; k < MAP_SIZE; k++) {
    			p = &disHashMap[k];
    			while (p != NULL) {
    				if (p->count > 1) {
    					ret += p->count * (p->count - 1);
    				}
    				p = p->next;
    			}
    		}
    	}
    	return ret;
    }
    

    0_1502863334966_捕获.PNG


Log in to reply
 

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