|
| 1 | +#defineALLOCATION_SIZE 100 // Allocation size of the numsArrLen in frequencyArrItem |
| 2 | + |
| 3 | +typedefstructhash_entry { |
| 4 | +intnum;/* we'll use this field as the key */ |
| 5 | +intcount; |
| 6 | +UT_hash_handlehh;/* makes this structure hashable */ |
| 7 | +}hash_entry; |
| 8 | + |
| 9 | +typedefstructfrequencyArrItem |
| 10 | +{ |
| 11 | +int*numsArr; |
| 12 | +intnumsArrLen; |
| 13 | +intindex;// Points to the first empty space in numsArr |
| 14 | +}frequencyArrItem; |
| 15 | + |
| 16 | +/** |
| 17 | + * Note: The returned array must be malloced, assume caller calls free(). |
| 18 | + */ |
| 19 | +int*topKFrequent(int*nums,intnumsSize,intk,int*returnSize){ |
| 20 | +int*result= (int*)malloc(k*sizeof(int)); |
| 21 | +*returnSize=k; |
| 22 | +intresultIndex=0;// Points to the first empty space in result |
| 23 | +hash_entry*NumFreqMap=NULL; |
| 24 | +frequencyArrItemfrequencyArr[numsSize+1];// Index is the count/frequency and the element is an array of numbers with this frequency |
| 25 | +memset(frequencyArr,0, (numsSize+1)*sizeof(frequencyArrItem));// Initialize with NULL and zeros |
| 26 | + |
| 27 | +for(inti=0;i<numsSize;i++) |
| 28 | + { |
| 29 | +hash_entry*retrievedMapEntry; |
| 30 | +HASH_FIND_INT(NumFreqMap,&nums[i],retrievedMapEntry); |
| 31 | + |
| 32 | +// If the number already exists in the map then increment its count |
| 33 | +if(retrievedMapEntry) |
| 34 | + { |
| 35 | +retrievedMapEntry->count+=1; |
| 36 | + } |
| 37 | +else |
| 38 | + { |
| 39 | +// If the number doesn't exist in the map then create a new map entry for it and add it to the map |
| 40 | +hash_entry*mapEntryToAdd= (hash_entry*)malloc(sizeof(hash_entry)); |
| 41 | +mapEntryToAdd->num=nums[i]; |
| 42 | +mapEntryToAdd->count=1; |
| 43 | +HASH_ADD_INT(NumFreqMap,num,mapEntryToAdd); |
| 44 | + } |
| 45 | + } |
| 46 | + |
| 47 | +// Loop over all the entries in the hash map |
| 48 | +for (hash_entry*mapEntry=NumFreqMap;mapEntry!=NULL;mapEntry=mapEntry->hh.next) { |
| 49 | +frequencyArrItem*freq=frequencyArr+mapEntry->count; |
| 50 | + |
| 51 | +// If the nums list for this frequency has not been created yet |
| 52 | +if(freq->numsArrLen==0) |
| 53 | + { |
| 54 | +freq->numsArrLen=ALLOCATION_SIZE; |
| 55 | +freq->numsArr= (int*)malloc(freq->numsArrLen*sizeof(int)); |
| 56 | + } |
| 57 | +// If the nums list exceeded the current allocated size, then reallocate |
| 58 | +elseif(freq->index==freq->numsArrLen) |
| 59 | + { |
| 60 | +freq->numsArrLen+=ALLOCATION_SIZE; |
| 61 | +freq->numsArr= (int*)realloc(freq->numsArr,freq->numsArrLen*sizeof(int)); |
| 62 | + } |
| 63 | + |
| 64 | +freq->numsArr[freq->index++]=mapEntry->num; |
| 65 | + } |
| 66 | + |
| 67 | +// Loop over the frequencies starting from the highest frequency |
| 68 | +for(inti=numsSize;i >=1;i--)// Note that we are looping until i == 1, as at index 0 it is just empty |
| 69 | + { |
| 70 | +frequencyArrItem*freq=frequencyArr+i; |
| 71 | +// If there is nums that exist at this particular frequency |
| 72 | +for(intj=0;j<freq->index;j++) |
| 73 | + { |
| 74 | +// If we have added all the elements we need to the result |
| 75 | +if(k--==0) |
| 76 | + { |
| 77 | +returnresult; |
| 78 | + } |
| 79 | + |
| 80 | +// Add the num to the result then increment the index |
| 81 | +result[resultIndex++]=freq->numsArr[j]; |
| 82 | + } |
| 83 | + } |
| 84 | + |
| 85 | +returnresult; |
| 86 | +} |