Share C solution with hash table


  • 0
    B

    my algorithm is:

    1. Create a struct of hash table, and store the first element as id in the hash[0]
    2. for i is 1 to numsSize do the following works:
      2.1. If the element is the same as previous element, repeat ++;
      2.2. If the element is new one, store it in hash table.
      2.3. the flag is for avoiding overlap. ( if the element is overlap, we don't need to store it.)
    3. Quick sort by the number of repeats.
    struct hashtable
    {
    	int repeat;
    	int id;
    	struct hashtable *next;
    };
    
    
    void swap(int *a, int *b){
    
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    
    int partitionStruct(  struct hashtable *hash,int low , int high){
    	int i,j; 
    	// int pivot = array[high];
    	int pivot = hash[high].repeat;
    	// the index of smaller element  
    	i = (low -1); 
    
    	for(j = low; j<= high -1 ; j++){
    
    		// if(hash[j].repeat <= pivot ){
    		if(hash[j].repeat > pivot ){  // from large to small
    			i++;
    			swap(&hash[i].repeat,&hash[j].repeat);
    			swap(&hash[i].id,&hash[j].id);
    		}
    	}
    
    	swap(&hash[i+1].repeat, &hash[high].repeat);
    	swap(&hash[i+1].id, &hash[high].id);
    	return(i+1);
    }
    
    
    void quickSortStruct( struct hashtable *hash,int low, int high){
    	if(low < high){
    		int pivot = partitionStruct(hash,low,high);
    
    		quickSortStruct(hash,low,pivot-1);
    		quickSortStruct(hash,pivot +1, high); 
    
    	}
    
    }
    
    
    int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
        
    	int i;
    	struct hashtable hash[numsSize];
    
    	int count = 0;
    	int index = 0;
    	int j =0;
    
        if(numsSize ==1 ){
    		*returnSize = 1;
    		return nums;
    	}
    	// store first id;
    	hash[0].id = nums[0];
    	hash[0].repeat =1;
    	int countHash = 1;
    	bool flag = false;
    	j = 0;
    	for ( i = 1; i < numsSize; i++)
    	{	
    		index = nums[i];
    		//printf("-----------Index:%d ------------\n",index );
    		flag = false;
    		j = 0;
    		//printf("J: %d countHash: %d \n",j,countHash );
    		while(j < countHash){
    			if(index == hash[j].id){	
    			//	printf("SAME ID: %d,  \n",hash[j].id);
    				hash[j].repeat++;
    				flag = true;
    				break;
    			}
    			j++;
    		}
    		if(flag == false){
    			hash[j].id = index;
    			hash[j].repeat =1;
    			countHash++;
    		}
    	}
    
    	quickSortStruct(hash,0,countHash-1);
    
    	int new_count = 0;
    	int *result = (int*)malloc(sizeof(int)*countHash);
    	int de_k = 0;
    	for (i = 0; i < countHash;i++)
    	{
    		if(de_k < k){
    			result[new_count] = hash[i].id;
    			new_count++;
    		}
    		//printf("ID %d: %d \n",hash[i].id,hash[i].repeat );
    		de_k ++;
    	}
    
    // 	for (i = 0; i < new_count;i++)
    // 	{
    // 		printf("RESULT: %d \n ",result[i] );	
    // 	}
    
    
        *returnSize = new_count;
    	return result;
    
    }
    

Log in to reply
 

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