692. 前K个高频单词-自定义哈希表和自定义快速排序

692. 前K个高频单词-自定义哈希表和自定义快速排序

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

示例 2：

输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

这一题用c语言做起来就是麻烦哎，不过博主还是做出来了，时间效率挺高的，解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */


 #define  sizeh  128
 struct hash{
     char *s;
     int size;
     int count;
     int index;
     struct hash *next;
 };
 void add_hash(struct hash *h,int size,char *s,int index){
     struct hash *p=(struct hash *)malloc(sizeof(struct hash));
     p->s=(char *)malloc(sizeof(char)*(size+1));
     p->count=1;
     p->size=size;
     p->index=index;
     char ch=s[size];
     s[size]='\0';
     strcpy(p->s,s);
     s[size]=ch;
     
     p->next=h->next;
     h->next=p;

 }
 bool find_hash(struct hash *h,int size,char *s){
     struct hash *p=h->next;
     char ch=s[size];
 
     while(p){
     
         if(p->size=size){
              s[size]='\0';
             int r=strcmp(p->s,s);
              s[size]=ch;
         
              if(r==0){
                  p->count++;
                  return true;
              }
            
         }
         p=p->next;
     }
    
     return false;

 }

void swap( char **a,char **b){
  
    *a=*b;
  


}

bool  my_strcmp(char *a,char *b,int acount,int bcount){
    if(acount>bcount){
        return true;
    }
    else if(acount<bcount){
        return false;
    }
    else{
        if(strcmp(a,b)>=0){
            return false;
        }
        else{
            return true;
        }
    }
    

}

void quick(char **s,int low,int high,int *r){
    if(low<high){
        int l=low,h=high,p=r[low];
          
        char *ch=(char *)malloc(sizeof(char)*(strlen(s[low])+1));
        strcpy(ch,s[low]);
      //  printf("%s ++",ch);
        while(low<high){
          
            while(low<high&&my_strcmp(s[high],ch,r[high],p)==false){
                high--;
            }
           
                swap(&s[low],&s[high]);
                r[low]=r[high];

            
           
            
            while(low<high&&my_strcmp(s[low],ch,r[low],p)==true){
                low++;
            }
        
                r[high]=r[low];
                swap(&s[high],&s[low]);

          
              
        }
       
        swap(&s[low],&ch);
        r[low]=p;
        quick(s,l,low-1,r);
        quick(s,low+1,h,r);
    }

}


char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize){
    int r[wordsSize];
      for(int i=0;i<wordsSize;i++){
        r[i]=0;
    }

     struct hash *h=(struct hash *)malloc(sizeof(struct hash)*sizeh);
   
  int i;

    for(i=0;i<sizeh;i++){
        (h+i)->next=NULL;
    }
    for( i=0;i<wordsSize;i++){
        if(find_hash(h+words[i][0]%sizeh,strlen(words[i]),words[i])==false){
            add_hash(h+words[i][0]%sizeh,strlen(words[i]),words[i],i);
        }

    }
  
    int size=0;
    
     for(i=0;i<sizeh;i++){
         struct hash *p=(h+i)->next;
         while(p){
          // printf(" -- %s %d",p->s,p->count);
        
             r[size]=p->count;
             swap(&words[size],&(p->s));
             size++;
             

         
             p=p->next;


         }
       
    }
   
    
    quick(words,0,size-1,r);
   
     
    *returnSize=k;
    return words;

  


}