当前位置： 移动技术网 > IT编程>开发语言>C/C++ > leadcode的Hot100系列--347. 前 K 个高频元素--hash表+直接选择排序

leadcode的Hot100系列--347. 前 K 个高频元素--hash表+直接选择排序

2019年07月12日  | 移动技术网IT编程  | 我要评论

北京市养老金,济宁采购,洪真卿

这个看着应该是使用堆排序，但我图了一个简单，所以就简单hash表加选择排序来做了。
使用结构体:

typedef struct node
{
    struct node *pnext;
    int value;  // 数值
    int frequency;  // 频率
}node_s;

思路：
hash表用来存储每个值对应的频率，每读到一个数字，对应的频率就加1。
然后从表中再把这些数据读取出来。
先创建两个长度为k的数组，一个用来记录频率，一个用来记录对应的数值。
读取数据的时候，使用频率做排序，在排序的时候，也要对应的交换数值的数组。


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

#define hash_len 10

typedef struct node
{
    struct node *pnext;
    int value;
    int frequency;
}node_s;

node_s *get_node(node_s **psthead, int num) // 获取num对应的节点
{
    int n;
    node_s *psttemp;
    if (num<0)
        n = -num;
    else
        n = num;
    psttemp = psthead[n%hash_len];
    
    while(null != psttemp)
    {
        if (num == psttemp->value)
            return psttemp;
        else
            psttemp = psttemp->pnext;
    }
    return psttemp;
}

void add_node(node_s **psthashhead, int num)   // 添加一个num的节点
{
    node_s *psttemp = null;
    node_s *pstnode = null;
    int i, n;
    
    if (num<0)     // 这里是防止给的num是负数
        n = -num;
    else
        n = num;
    
    psttemp = get_node(psthashhead, num);
    if (null == psttemp)
    {
        psttemp = (node_s *)calloc(1, sizeof(node_s));
        if (null == psttemp) return;
        psttemp->value = num;
        psttemp->frequency = 1;
        pstnode = psthashhead[n%hash_len];
        if (null == pstnode)
            psthashhead[n%hash_len] = psttemp;   // 说明是第一个节点
        else
        {
            while (null != pstnode->pnext) // 往后面继续挂链表
            {
                pstnode = pstnode->pnext;
            }
            pstnode->pnext = psttemp;
        }
    }
    else
    {
        (psttemp->frequency) ++; // 已经有该节点，则直接频率加1
    }
    return;
}

void swap(int *frequency, int *value, int i, int k)  // 交换频率的时候，也要交换对应的数值
{
    int temp = frequency[i];
    frequency[i] = frequency[k];
    frequency[k] = temp;
    temp = value[i];
    value[i] = value[k];
    value[k] = temp;
    return;
}

void selectsort(int *frequency, int *value, int len) // 选择排序
{
    for(int i=0;i<len-1;i++)
    {
        int min = frequency[len-1-i];
        int local = len-1-i;
        for(int j=0;j<len-1-i;j++)
        {
            if(min > frequency[j])
            {
                min = frequency[j];
                local = j;
            }
        }

        if(local != (len-1-i))
            swap(frequency, value, local, len-1-i);
    }
}

int* topkfrequent(int* nums, int numssize, int k, int* returnsize){
    node_s *psthashheadvalue[hash_len] = {0};
    node_s *psttemp = null;
    int *ptmp, i;
    int *pifrequency = null, *pivalue = null;
    
    for (i=0; i<numssize; i++)  // 把所有元素都插入到hash表中
    {
        add_node(psthashheadvalue, nums[i]);
    }
    
    // 这里生成两个数组，一个频率数组，一个数值数组，频率数组用来排序， 数值数组用来返回
    pifrequency = (int *)calloc(k, sizeof(int));   
    if (null == pifrequency) return null;
    pivalue = (int *)calloc(k, sizeof(int));
    if (null == pivalue) return null;
    
    int count = 0;
    for (i=0; i<hash_len; i++)
    {
        if (null != psthashheadvalue[i])
        {
            node_s *psttemp = psthashheadvalue[i];
            while (null != psttemp)
            {
                if (count<k)
                {
                    pifrequency[count] = psttemp->frequency;
                    pivalue[count] = psttemp->value;
                    count ++;
                    if (count == k)
                        selectsort(pifrequency, pivalue, k);  // 把数组填满之后，先做一次排序
                }
                else
                {
                    if (psttemp->frequency > pifrequency[k-1])   // 只有当该频率大于当前存储最小频率的时候，才需要进行重新排序
                    {
                        pifrequency[k-1] = psttemp->frequency;
                        pivalue[k-1] = psttemp->value;
                        selectsort(pifrequency, pivalue, k);
                    }
                }
                psttemp = psttemp->pnext;
            }
        }
    }

    *returnsize = k;
    return pivalue;
    
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网