[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;
}