[347] Top K Frequent Elements

感人！！！
我竟然寫出來惹  XDDDD
（又不是什麼世界難的題目, 感動屁XD）
（何況妳好像沒有達到題目要求的 O(nlogn) 吧 XD）
（不管啦可是我跑出來時間很快耶XD）
（重點是我有寫出來就偷笑啦還管什麼Time Complexity啊！）
（但那就是人家要考的東西啊妳XD）
（跳一下）（根本是跳很多下）
這題就是說要找出出現次數最多次的前k 個
比方說1,1,1,2,2,3 要找 k = 2 的話就是 1跟2 因為它們出現三次跟兩次是最多次的前兩組
一開始想亂寫用兩個hash先hash過來再hash回去
發現那如果出現次數一樣的話, 它就消失了XD（magic ~~~~~）
才知道原來又要使用到bucket sort 了 QQ
要記住若是排序的根據有兩個, 就要用bucket sort呀記起來好嗎～～～～～～
比方說撲克牌要照花色大小排列, 那就是bucket sort的使用時機惹～～～
像這題就是....（咦？！XD）

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

typedef struct _BucketArray
{
    int value;
    int count;
}BucketArray;  

void addBucket(BucketArray *bucket,int size, int count, int num){
//    printf("count %d num %d\n", count, num);
    for (int i =0 ; i<size; i++)
    {
        if (count > bucket[i].count)
        {
            if (bucket[i].count != 0)
                for (int j=size-1;j>i; j--)
                {
                    bucket[j].value = bucket[j-1].value;
                    bucket[j].count = bucket[j-1].count;
                }
            bucket[i].value = num;
            bucket[i].count = count;
            break;
        }
    }
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
    int *ret = malloc(sizeof(int)*k);
    *returnSize = k;
    int max = INT_MIN;
    int min = INT_MAX;
    int i,j;
    for(i=0; i<numsSize;i++)
    {
        if(nums[i] > max)
            max = nums[i];
        if(nums[i] < min)
            min = nums[i];
    }
//index + min
//hash = 出現次數  
    int hashSize= max-min+1;
    int *hash = malloc(sizeof(int)*(hashSize));
    memset(hash,0,sizeof(int)*hashSize);

    for(i=0; i<numsSize;i++)
        hash[nums[i]-min]++;

    BucketArray *bucket= malloc(sizeof(BucketArray)*k);
    memset(bucket,0,sizeof(BucketArray)*k);
    for (i=0;i<hashSize;i++)
    {
        addBucket(bucket,k, hash[i], i+min);
    }
    for (i=0;i<k;i++)
        ret[i] = bucket[i].value;
    return ret;
}
[20251029]更新

其實我看不懂當年我在寫什麼 囧 先來個qsort 版本

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

struct hash{

int val;

int freq;

};

int comp(void const *a, void const *b){

return ((*(struct hash**)b)->freq -(*(struct hash**)a)->freq );

}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {

struct hash **myHash = calloc (20001 , sizeof(struct hash*));

for (int i=0; i<20001; i++)

myHash[i]= calloc (1, sizeof(struct hash));

for (int i=0; i<numsSize; i++)

{

int idx = nums[i]+10000;

myHash[idx]->freq ++;

myHash[idx]->val = nums[i];

}

qsort((void *)myHash,20001, sizeof(struct hash*),comp);

int *ret= calloc(k, sizeof(int));

for (int i=0; i<k; i++)

ret[i]= myHash[i]->val;

*returnSize =k;

return ret;

}

之後再來個heap 版本 ？！

[20251111] 失敗了 XD 不想寫heap XD

用了先sort , 再依序把出現次數算出來，再丟去一個二維array, index是出現次數，若有相同出現次數的則往後長 

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int comp(const void *a, const void *b){

return (*(int*)a-*(int*)b);

}

struct freq{

int val;

int count;

};

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {

qsort(nums, numsSize, sizeof(int), comp);

struct freq *hash = calloc (numsSize, sizeof(struct freq));

int idx = 0;

int max = INT_MIN;

for (int i=0; i<numsSize; i++)

{

int count =1;

while (i<numsSize-1 && nums[i]==nums[i+1]){

count++;

i++;

}

hash[idx].count=count;

hash[idx].val=nums[i];

if (hash[idx].count>max)

max = hash[idx].count;

idx++;

}

int **queue = calloc (max+1, sizeof(int *));

int *q_idxs=calloc (max+1, sizeof (int));

for (int i=0; i< max+1; i++){

queue[i]= calloc (numsSize, sizeof (int));

}

for (int i=0; i<idx; i++){

int tmp = hash[i].count;

queue[tmp][q_idxs[tmp]]= hash[i].val;

q_idxs[hash[i].count]++;

}

*returnSize = 0;

int *ret = calloc (numsSize, sizeof (int));

for (*returnSize =0; *returnSize < k;){

//find index

for (int j=0; j< q_idxs[max]; j++)

ret[(*returnSize)++]= queue[max][j];

max--; // we have used one max count

while (max>=0 && q_idxs[max]==0)

max--;

}

return ret;

}