这个看着应该是使用堆排序，但我图了一个简单，所以就简单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 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 psttemp="get_node(pstHashHead," num); if (null="=" psttemp) { *)calloc(1, sizeof(node_s)); 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];" 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" pivalue) int count="0;" for (i="0;" i<hash_len; !="pstHashHeadValue[i])" node_s *psttemp="pstHashHeadValue[i];" while (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;
}
</numssize;></len-1;i++)></0)></0)>
Original: https://www.cnblogs.com/payapa/p/11173705.html
Author: 努力爬呀爬
Title: leetcode的Hot100系列–347. 前 K 个高频元素–hash表+直接选择排序
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/565233/
转载文章受原作者版权保护。转载请注明原作者出处！