leetcood

leetcood,第1张

  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;
}
  1. 时间复杂度?空间复杂度?
  2. (方法二)解题思路:
    (1)将每一个数组nums元素放进哈希表中,以元素值作为键,并为每个元素出现次数计数;
    (2)建立大小为 k 的小顶堆,比较后续元素和堆顶元素count值,如果后续元素比较大,则将堆顶元素替换成新元素值,将替换后的堆进行小顶堆的筛选,保证堆顶元素的最小的(中间元素不一定非要严格按照从小到大排序)。


  3. (方法二)代码:
/**
 * 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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/563422.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存