leetcood

1. 题目描述：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
   

   
   

   你可以按任意顺序 返回答案。
   

   
   

2. 示例
   输入: nums = [1,1,1,2,2,3], k = 2
   输出: [1,2]

   输入: nums = [1], k = 1
   输出: [1]

3. 提示

   1 <= nums.length <= 105

   k 的取值范围是 [1, 数组中不相同的元素的个数]，题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

4. 前 K 个高频元素

5. （方法一）解题思路：
   （1）将每一个数组nums元素放进哈希表中，以元素值作为键，并为每个元素出现次数计数；
   （2）给节点排序，uthash库中包含了哈希表的查询、插入、删除和排序等功能，包含的 HASH_SORT 函数可以根据key或者count值对哈希表的内容进行排序。
   

   
   

   本题应当依据count值进行从大到小排序，最后依次输出前k个哈希表的key值。
   

   
   

6. （方法一）代码：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct hash_table {
    int ikey;    // 键值nums[i]
    int count;  // 计数
    UT_hash_handle hh;
};
struct hash_table *h;
struct hash_table* find(int ikey)
{
    struct hash_table *s = NULL;
    HASH_FIND_INT(h,&ikey,s);
    return s;
}
void insert(int ikey)
{
    struct hash_table *s = find(ikey);
    if(s==NULL)
    {
        s = (struct hash_table*)malloc(sizeof(struct hash_table));  
        s->ikey = ikey;  
        s->count = 1;
        HASH_ADD_INT(h, ikey, s);
    }
    else
    {
        s->count++;
    }
}
// 类似于qsort函数里的cmp函数，确定排序是从大到小还是从小到大
int count_sort(struct hash_table *a, struct hash_table *b) {
	   return (b->count - a->count);//依据count值从大到小排序
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    *returnSize = k;
    h = NULL;
    for(int i=0;i<numsSize;i++)
    {
        insert(nums[i]);
    }
    int *ret = (int*)malloc(sizeof(int)*k);
    // 对哈希表依据count值进行排序
    HASH_SORT(h, count_sort);
    struct hash_table *s;
    int index = 0;
    for(s = h;index < k; s = s->hh.next) 
    {
        ret[index++] = s->ikey;
    }
    return ret;
}

7. 时间复杂度？空间复杂度？
8. （方法二）解题思路：
   （1）将每一个数组nums元素放进哈希表中，以元素值作为键，并为每个元素出现次数计数；
   （2）建立大小为 k 的小顶堆，比较后续元素和堆顶元素count值，如果后续元素比较大，则将堆顶元素替换成新元素值，将替换后的堆进行小顶堆的筛选，保证堆顶元素的最小的（中间元素不一定非要严格按照从小到大排序）。
   

   
   

9. （方法二）代码：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 // 时间复杂度：O(Nlogk)
 // 空间复杂度：O(N)
struct hash_table {
    int ikey;    // 键值nums[i]
    int count;  // 计数
    UT_hash_handle hh;
};
struct pairs{
    int val;
    int count;
};
struct pairs *heap;
struct hash_table *h;
// 哈希表的插入函数
void insert(int ikey)
{
    struct hash_table *s = NULL;
    HASH_FIND_INT(h,&ikey,s);
    if(s==NULL)
    {
        s = (struct hash_table*)malloc(sizeof(struct hash_table));  
        s->ikey = ikey;  
        s->count = 1;
        HASH_ADD_INT(h, ikey, s);
    }
    else
    {
        s->count++;
    }
}
// 交换
void swap(struct pairs* i, struct pairs* j)
{
	struct pairs temp = *i;
	*i = *j;
	*j = temp;
}
// 建立小顶堆的过程，最顶上的元素一定是最小的
void build_little_heap(int start,int end)
{
    for (int index = 2 * start + 1;index <= end;index=2* index+1)
	{
		if (index < end && heap[index].count > heap[index + 1].count)
		{
			index++;
		}
		if (heap[start].count <= heap[index].count)
		{
			break;
		}
		swap(heap + start, heap + index);
		start = index;
	}
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    *returnSize = k;
    h = NULL;
    for(int i=0;i<numsSize;i++)
    {
        insert(nums[i]);
    }
    heap = (struct pairs*)malloc(sizeof(struct pairs)*(k+1));
    int *heapSize = malloc(sizeof(int));
    *heapSize = 0;
    struct hash_table *s,*tmp;
    // HASH_ITER(hh, h, s, tmp)
    for (s = h; s != NULL; s = s->hh.next)
    {
        if(*heapSize >= k)  // 元素数目超过小顶堆元素数目，需要将堆顶元素d出，替换成要加进去的元素
        {
            struct pairs tmp = heap[0];
            if(tmp.count < s->count)
            {
                heap[0].val = s->ikey;
                heap[0].count = s->count;
                for(int i=*heapSize/2-1;i>=0;i--)//重复建立小顶堆的过程，保证堆顶元素最小
                {
                    build_little_heap(i,*heapSize-1);
                }
            }
        }
        else// 元素数目不超过小顶堆元素数目，将元素 放入堆底
        {
            heap[*heapSize].val = s->ikey;
            heap[(*heapSize)++].count = s->count;
            for(int i=*heapSize/2-1;i>=0;i--)
            {
                build_little_heap(i,*heapSize-1);//重复建立小顶堆的过程，保证堆顶元素最小
            }
        }
    }
    int* ret = (int*)malloc(sizeof(int)*k);
    for(int i=0;i<k;i++)
    {
        ret[i] = heap[i].val;
    }
    return ret;
}