TOP

leadcode的Hot100系列--347. 前 K 个高频元素--hash表+直接选择排序
2019-07-12 02:10:04 】 浏览:159
Tags:leadcode Hot100 系列 --347. 高频 元素 --hash 直接 选择 排序

这个看着应该是使用堆排序,但我图了一个简单,所以就简单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;
    
}


leadcode的Hot100系列--347. 前 K 个高频元素--hash表+直接选择排序 https://www.cppentry.com/bencandy.php?fid=45&id=227559

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇结构体初始化 下一篇算法-约瑟夫问题