347. 前 K 个高频元素

题目链接 https://leetcode-cn.com/problems/top-k-frequent-elements/

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

uthash + 快速选择

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct hash_table
{
    int k;
    int v;
    UT_hash_handle hh;
};

typedef struct hash_table* hash_ptr;

struct pair
{
    int first;
    int second;
};
typedef struct pair* pair_ptr;

void swap(pair_ptr i, pair_ptr j)
{
    struct pair t = *i;
    *i = *j;
    *j = t;
}

void quick_find(struct pair* res, int left, int right, int target_position)
{
    if(left >= right) return;
    int last = left;
    int i;

    for(i=left+1; i<=right; i++)
    {
        if(res[i].first >= res[left].first)
        {
            last++;
            swap(&res[last], &res[i]);
        }
    }
    swap(&res[last], &res[left]);
    if(last == target_position)
        return;
    if(last > target_position)
    {
        return quick_find(res, left, last-1, target_position);
    }
    if(last < target_position)
    {
        return quick_find(res, last+1, right, target_position);
    }

}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    hash_ptr head = NULL;
    hash_ptr p = NULL, tmp = NULL;

    int i;
    int size = 0;
    int* result = malloc(k * sizeof(int));

    for(i=0; i<numsSize; ++i)
    {
        HASH_FIND_INT(head, &nums[i], p);
        if(p == NULL)
        {
            p = malloc(sizeof(struct hash_table));
            p->k = nums[i];
            p->v = 1;
            HASH_ADD_INT(head, k, p);
        }
        else
        {
            p->v++;
        }
    }

    struct pair data[numsSize];
    HASH_ITER(hh, head, p, tmp)
    {
        data[size].first = p->v;
        data[size].second = p->k;
        size++;
    } 

    quick_find(data, 0, size-1, k-1);

    for(i=0; i<k; ++i){
        result[i] = data[i].second;
    }
    *returnSize = k;

    return result;
}

还有一个水题的办法

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int res[6700][2];

int offset = 3350;

int tmp = 6700+100;

void swap(int i, int j)
{
    int t;
    t = res[i][0];
    res[i][0] = res[j][0];
    res[j][0] = t;

    t = res[i][1];
    res[i][1] = res[j][1];
    res[j][1] = t;
}

void quick_find(int left, int right, int target_position)
{
    if(left >= right) return;
    int last = left;
    int i;

    for(i=left+1; i<=right; i++)
    {
        if(res[i][0]>=res[left][0])
        {
            last++;
            swap(last, i);
        }
    }
    swap(last, left);
    if(last == target_position)
        return;
    if(last > target_position)
    {
        return quick_find(left, last-1, target_position);
    }
    if(last < target_position)
    {
        return quick_find(last+1, right, target_position);
    }

}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    int i;
    int size = 0;
    int* f = malloc(k * sizeof(int));

    int d[tmp];
    for(i=0;i<tmp;++i) d[i]=0;
    for(i=0; i<numsSize; ++i){
        d[nums[i]+offset] += 1;
    }

    for(i=0; i<tmp; ++i){
        if(d[i] > 0){
            res[size][0] = d[i];
            res[size][1] = i;
            size++;
        }
    }
    

    quick_find(0, size-1, k-1);

    for(i=0; i<k; ++i){
        f[i] = res[i][1]-offset;
    }
    *returnSize = k;

    return f;
}