leetcode121，leetcode的Hot100系列--347. 前 K 個高頻元素--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 10typedef 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;elsen = num;pstTemp = pstHead[n%HASH_LEN];while(NULL != pstTemp){if (num == pstTemp->value)return pstTemp;elsepstTemp = 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;elsen = 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;}